Tuesday, October 29, 2013

Subset sum problem

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.