Given a set of numbers and a target value, we have to find if there is any subset whose sum is equal to the target value.

For example let the array be {10, 34, 19, 27, 58, 45} and the target sum is 56, we have a subset {10,19,27} with the given sum. We don’t have any subset with sum 100.

A simple recursive solution can be given as follows. We pass the array, the starting index, and target sum to the function.

At each index we have two choices:

- Include the current element and search for {sum – current_num} in the remaining set of elements.
- Exclude the current element and search for sum in the remaining set of elements.

public static boolean hasSum(int [] array, int start, int sum)

{

if( sum == 0 ) //found the sum?

return true;

if( start > array.length-1 )//reached end of the array?

return false;

return hasSum(array, start+1, sum) || hasSum(array, start+1, sum-array[start]);

}

But this algorithm has an exponential time complexity which is not efficient.

Let us look at more efficient approach based on Dynamic programming.

We take a boolean matrix of size (sum+1) x (N+1) where sum is the target sum and N is the size of the given set.

matrix[i][j] = true; indicates that there is a subset of array[0..j-1] which contains the sum i.

We initialize the following entries as base values.

- matrix[0][j] = true; where 1 <= j <= N since in any set there will be empty subset with sum 0;
- matrix[i][0] = false; where 1 <= i <= sum since we can’t find a sum > 0 in an empty array.

We calculate the remaining entries as follows.

matrix[i][j] = matrix[i][j-1];

If there exists a subset of array[0..j-2] with the sum i; then there should be a subset of array[0..j-1]also with the sum i.

If i >= array[j-1]; we check to see if matrix[i – array[j-1]][j-1] is true. This means check if there is any subset of array[0..j-2] with sum i-array[j-1].

If there is, then we assign true to this entry.

Finally we return the value at matrix[sum][N] which indicates true if there is a subset of array[0..N-1] with the given sum. Otherwise false.

Here is the Java code which implements this.