2

Possible Duplicate:
Sum-subset with a fixed subset size

So I have an array A, with elements A[1], A[2] .. A[N]

I want to find a subsequence (not necessarily contiguous), with exactly K elements, whose sum is exactly Sum.

My best guess is of O(NK), if you run K nested loops, and test every possibility.

Can this be done faster?

All elements of A are integers, greater than 0.

Community
  • 1
  • 1
user1527166
  • 3,229
  • 5
  • 26
  • 26

1 Answers1

1

I think this cannot be solved in polinomial time. @Anderson is right, it does resemble the knapsack problem.

Although you can make it faster by a branch and bound algorithm, but it's effectiveness will be based on your actual values. (eg: if you exceed the sum, don't test further)

Edit: Based on the topic, what @amit linked, O(n^k) is indeed the best answer, which is polinomial in n, for any fixed k value.

szegedi
  • 863
  • 8
  • 20