abdalimran's blog

Problem: Searching N elements from an array which sum is X
By abdalimran, 10 years ago, In English

You are given S,X and N.

S = size of an array

N = number of elements you have to find

X = sum

You have to find N elements from the array which sum is X.

Input:

7 25 3

1 5 10 7 13 15

Output:

5 7 13

If there are multiple solution you can output any of them. What are the best possible solutions with least complexity for this problem?

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The best complexity may depend on the constraints. What are they?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is NP-complete (if we let X be 0 and then enumerate all possible N, we solve subset sum problem).

Nevertheless, you can do pseudo polynomial knapsack-like solution. Denote array A and its elements as A1, ..., An. Let OPT(x, i, n) be equal true if we can get sum x choosing n elements from {A1, ..., Ai} (the first i elements of A) and false otherwise. We can recalculate it as following:

→ Reply