0

The problem is as follows: you are given n (1->1000) and k(1->100), find the number of possible ways to pick numbers from 1 to k so that their sum is equal to n.

Here is an example:

n = 5; k = 3;

Possible ways:

1*3 + 1*2 = 5

1*3 + 2*1 = 5

1*2 + 3*1 = 5

2*2 + 1*1 = 5

5*1 = 5

==> We get 5 possible ways

I've tried combinations, writing down many examples to find the universal solution but no luck.

Please help me with this, thanks!

Henry Anh
  • 19
  • 5

1 Answers1

2

The problem that you described is known as partitions. It requires recurrence to get the solution. I adapted my solution from this question which contains detailed explanation of the idea. Be careful because this number grows really fast, for instance for n = 100 and k = 6 you'll get 189509 possible sums. Here's the code in C++:

#include <string>
#include <algorithm>

int nrOfSums = 0;
void partition(int n, int max, std::string prefix) {
    if (n == 0) {
        std::cout<<prefix<<std::endl;
        nrOfSums++;
        return;
    }

    for (int i = std::min(max, n); i >= 1; i--) {
        partition(n - i, i, prefix + " " + std::to_string(i));
    }
}
void partition(int n, int k) {
    partition(n, k, "");
}


int main()
{
    int n = 8, k = 3;
    partition(n, k);
    std::cout << "number of possible sums: "<< nrOfSums;
}

And the output for n = 8, k = 3:

 3 3 2
 3 3 1 1
 3 2 2 1
 3 2 1 1 1
 3 1 1 1 1 1
 2 2 2 2
 2 2 2 1 1
 2 2 1 1 1 1
 2 1 1 1 1 1 1
 1 1 1 1 1 1 1 1
number of possible sums: 10
Piotr Siekański
  • 1,665
  • 8
  • 14