Solve the k-sum problem: determine if there exist k elements in the input array that sum to a given target sum. Assumption: values may be reused as many times as we want (extremely unclear from the book which version they want us to solve).

[Chinmay26]

Can this be reduced to permutation sum and subset sum problems?

1. If values cannot be reused ==reduces to==> Get a subset of k elements whose sum = target. Using DP, we have a pseudo polynomial in O(N * target_sum)
2. If values can be reused ==reduces_to==> Get a permutation sum of k elements whose sum = target. Using DP, we can again have a pseudo polynomial in O(N * target_sum) ?

[Apollys]

I see what you're getting at - applying the knapsack DP idea to this scenario.

The complexity analysis and optimal algorithm design gets a little trickier with negative numbers permitted. I'll add it to the write-up when I get a chance!