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.