Subsets of a given Set of Integers whose sum is a Constant N : Java

Given a set of integers, how to find a subset that sums to a given value.开发者_JAVA技巧..the subset problem ?

Example : S = {1,2,4,3,2,5} and n= 7 Finding the possible subsets whose sum is n. I tried to google out found many links,but were not clear. How can we solve this in java and what is the data structure to be used and its complexity ?

In three steps:

1. Find the powerset of S (the set of all subsets of S)

2. Compute the sum of each subset

3. Filter out subsets that did not sum to 7.

I wont give you any code, but explain how it works.

1. Run a loop from 0 to (2^k-1)
2. For each value in 1, a 1 in its binary representation indicates that this value is chosen and 0 otherwise.
3. Test to see if the sum of chosen numbers is equal to n.

The above method will evaluate each possible subset of the given set.

If the upper limit of the values is small, then Dynamic Programming Approach could be used.