13

Given an unsorted set of integers in the form of array, find all possible subsets whose sum is greater than or equal to a const integer k, eg:- Our set is {1,2,3} and k=2

Possible subsets:-

 {2},
 {3},
 {1,2},
 {1,3},
 {2,3}, 
 {1,2,3}

I can only think of a naive algorithm which lists all the subsets of set and checks if sum of subset is >=k or not, but its an exponential algorithm and listing all subsets requires O(2^N). Can I use dynamic programming to solve it in polynomial time?

8
  • If you are interested in printing or listing all these subsets then in worst case you may still have 2^N-1 (all apart from empty) subsets that you need to list. You could however count how many there are with dynamic programming in polynomial.
    – cyon
    Aug 6, 2013 at 16:38
  • @cyon, How can we count the number of such subsets using dynamic programming?
    – Hidetoshi
    Aug 6, 2013 at 16:48
  • 5
    Finding if there is a subset which sums to k, is NP-Hard (Subset Sum Problem) - so, this question as well. And since you want the actual sets, seems to me that brute forcing generating all subsets is the way to go. (might add some optimizations using branch and bound techniques, but that's about it, IMO)
    – amit
    Aug 6, 2013 at 16:51
  • 3
    @amit The Subset Sum Problem refers to finding a subset that sums to exactly k, not at least k. Finding a subset that sums to at least k is O(n) (just add up everything and see if the sum is big enough).
    – dfan
    Aug 6, 2013 at 17:12
  • 1
    @dfan But the question is about finding ALL subsets which are greater/equal k. To do this, you need to find all subsets that sums to k. Finding them out, is NP-Hard.
    – amit
    Aug 6, 2013 at 17:14

3 Answers 3

11

Listing all the subsets is going to be still O(2^N) because in the worst case you may still have to list all subsets apart from the empty one.

Dynamic programming can help you count the number of sets that have sum >= K

You go bottom-up keeping track of how many subsets summed to some value from range [1..K]. An approach like this will be O(N*K) which is going to be only feasible for small K.

The idea with the dynamic programming solution is best illustrated with an example. Consider this situation. Assume you know that out of all the sets composed of the first i elements you know that t1 sum to 2 and t2 sum to 3. Let's say that the next i+1 element is 4. Given all the existing sets we can build all the new sets by either appending the element i+1 or leaving it out. If we leave it out we get t1 subsets that sum to 2 and t2 subsets that sum to 3. If we append it then we obtain t1 subsets that sum to 6 (2 + 4) and t2 that sum to 7 (3 + 4) and one subset which contains just i+1 which sums to 4. That gives us the numbers of subsets that sum to (2,3,4,6,7) consisting of the first i+1 elements. We continue until N.

In pseudo-code this could look something like this:

int DP[N][K];
int set[N];

//go through all elements in the set by index
for i in range[0..N-1]
   //count the one element subset consisting only of set[i]
   DP[i][set[i]] = 1

   if (i == 0) continue;

   //case 1. build and count all subsets that don't contain element set[i]
   for k in range[1..K-1]
       DP[i][k] += DP[i-1][k]

    //case 2. build and count subsets that contain element set[i]
    for k in range[0..K-1] 
       if k + set[i] >= K then break inner loop                     
       DP[i][k+set[i]] += DP[i-1][k]

//result is the number of all subsets - number of subsets with sum < K
//the -1 is for the empty subset
return 2^N - sum(DP[N-1][1..K-1]) - 1
5
  • Can you please tell me how to do this part --> sum(DP[1...K]
    – Rasool
    May 27, 2014 at 12:12
  • @Rasoolll What I mean by that is sum = DP[1] + DP[2] + .. + DP[K]
    – cyon
    May 27, 2014 at 12:41
  • DP is a two-dimension array, so DP[0] + ... + DP[K] is not true I think
    – Rasool
    May 27, 2014 at 12:42
  • @Rasoolll Oh yes, apologies I didn't pay attention. sum = DP[N-1][1] + DP[N-1][2] + .. + DP[N-1][K-1]. Because you are trying to find out for sets consisting of up to N (N-1 because indexed from 0) how many sum to either 1,2,3,..K-1. When you figure out how many, you subtract this from all subsets to get how many there are that sum to K, K+1, etc. My mistake for not explaining it well in the code.
    – cyon
    May 27, 2014 at 12:50
  • Let us continue this discussion in chat.
    – cyon
    May 27, 2014 at 13:15
6

Can I use dynamic programming to solve it in polynomial time?

No. The problem is even harder than @amit (in the comments) mentions. Finding if there exists a subset that sums to a specific k is the subset-sum problem, which is NP-hard. Instead you are asking for how many solutions are equal to a specific k, which is in the much more difficult class of P#. In addition, your exact problem is slightly more difficult since you want to not only count, but enumerate all the possible subsets for k and targets < k.

1

If k is 0, and every element of the set is positive then you have no choice but to output every possible subset, so the lower-bound to this problem is O(2N) -- the time taken to produce the output.

Unless you know something more about the value k that you haven't told us, there's no faster general solution that to just check every subset.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.