Knapsack with max element count in subsets

Question

i have an integer array, and i need to find a subset of this array with max 3 elements which is equal to W.

Can i solve this problem using knapsack? or i need to calculate every 1-2-3 element combination of the array?

Thanks already

Answer 1

To look for 3 elements that sum to W, this is exactly the 3SUM problem.

It can be solved in O(n²) time by either:

• Inserting each number into a hash table, then, for each combination of two numbers a and b, checking whether W-a-b exists in the hash table.

• Sorting the array, then, for each element a, looking right for two elements that sums to W-a using 2 iterators from either side.

If the integer range is in the range [-u, u], you can solve your problem using a Fast Fourier transform in O(n + u log u). See the above link for more details on either this or one of the above approaches.

Since your problem is dependent on solving 3SUM, which is a well-known problem, you're very unlikely to find a solution with better running time than the above well-known solutions for 3SUM.

To look for 1 element:

You can do a simple linear search (O(n)).

To look for 2 elements:

This can be solved by simply checking each combination of 2 elements in O(n²) (you needn't do something more complex as the asymptotic running time of 3 elements will result in O(n²) total time regardless of how efficient this is).

It can also be solved in O(n) or O(n log n) using methods identical to those described above for 3SUM.

Overall running time:

O(n²) or O(n + u log u), depending on which method was used to solve the 3SUM part.