Question

Write a program using "memoization" in order to calculate n choose k (permutation of subsets)? Here's what I got so far but can't seem to get the last 3 functions to produce the correct value. Any suggestions on how to fix it?

#include <iostream>

using namespace std;

int values[1000][1000] = { (int)0 };

int n_choose_k(int n, int k) {
   if (k == 0)
       return (int)1;
   if (n == k)
       return (int)1;
   if (values[n][k] != 0)
       return values[n][k];
   return values[n][k] = (n_choose_k(n - 1, k - 1) + n_choose_k(n - 1, k)) % 100000000;
}

int main() {
   cout << n_choose_k(10, 5) << endl;
   cout << n_choose_k(20, 10) << endl;
   cout << n_choose_k(30, 15) << endl; // should be 155117520 but I get 55117520
   cout << n_choose_k(39, 15) << endl; // should be 25140840660
   cout << n_choose_k(39, 14) << endl; // should be 15084504396
   cout << n_choose_k(40, 15) << endl; //should be 40225345056
   system("pause");

   return 0;
}

Answer 1

• Change the datatype as unsigned long long so that it can hold the larger value.
• No need of doing mod with 1000000 because you are not calculating ncr modulo k

Code

#include <iostream>

using namespace std;

unsigned long long values[1000][1000] = { (int)0 };

unsigned long long n_choose_k(int n, int k) {
if (k == 0)
return (int)1;
if (n == k)
return (int)1;
if (values[n][k] != 0)
return values[n][k];
return values[n][k] = n_choose_k(n - 1, k - 1) + n_choose_k(n - 1, k);
}

int main() {
cout << n_choose_k(10, 5) << endl;
cout << n_choose_k(20, 10) << endl;
cout << n_choose_k(30, 15) << endl; // should be 155117520 but I get 55117520
cout << n_choose_k(39, 15) << endl; // should be 25140840660
cout << n_choose_k(39, 14) << endl; // should be 15084504396
cout << n_choose_k(40, 15) << endl; //should be 40225345056
system("pause");

return 0;
}

Test Output