Number of ways to represent a number as a sum of K numbers in subset S

Question

Let the set S be {1 , 2 , 4 , 5 , 10}

Now i want to find the number of ways to represent x as sum of K numbers of the set S. (a number can be included any number of times)

if x = 10 and k = 3

Then the ans should be 2 => (5,4,1) , (4,4,2) The order of the numbers doesn't matter ie.(4,4,2) and (4,2,4) count as one.

I did some research and found that the set can be represented as a polynomial x^1+x^2+x^4+x^5+x^10 and after raising the polynomial to the power K the coefficients of the product polynomial gives the ans.

But the ans includes (4,4,2) and (4,2,4) as unique terms which i don't want

Is there any way to make (4,4,2) and (4,2,4) count as same term ?

Answer 1

This is a NP-complete, a variant of the sum-subset problem as described here.

So frankly, I don't think you can solve it via a non-exponential (iterate though all combinations) solution, without any restrictions on the problem input (such as maximum number range, etc.).

Without any restrictions on the problem domain, I suggest iterating through all your possible k-set instances (as described in the Pseudo-polynomial time dynamic programming solution) and see which are a solution.

Checking whether 2 solutions are identical is nothing compared to the complexity of the overall algo. So, a hash of the solution set-elements will work just fine:

E.g. hash-order-insensitive(4,4,2)==hash-order-insensitive(4,2,4) => check the whole set, otherwise the solutions are distinct.

PS: you can also describe step-by-step your current solution.