Given a set of n integers, list all possible subsets with sum>=k

algorithm

Solution

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

Problem

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?

Original source