0
$\begingroup$

Given an array of positive integers and a positive integer K, I need to find the minimum subset sum S greater than K, and the size of the smallest subset that sums to S.

I have attempted to first find the minimum subset sum greater than K with a 0-1 knapsack approach, then finding the smallest subset that sums to that value, but that approach was too slow. I have also attempted iterating through the array, and storing the combinations of (subset sum, subset size) and discarding the values greater than K that were not the minimum, however this approach was also too slow.

$\endgroup$
1
  • $\begingroup$ What's the order of magnitude of the array size and the integers in it? 10 000 elements array of integers up to 100? 10 000 000 elements array of integers up to 10 000 000 000 000? $\endgroup$ Mar 12 at 9:49

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.