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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* To change this template, choose Tools | Templates | |
* and open the template in the editor. | |
*/ | |
package subsetsum; | |
/** | |
* | |
* @author Ravi | |
*/ | |
public class SubsetSum { | |
/** | |
* @param args the command line arguments | |
*/ | |
public static void main(String[] args) { | |
int [] array = {63, 21, 78, 45, 59, 62, 37, 22, 19, 101}; | |
if( hasSum(array, 200) ) | |
System.out.println("Yes"); | |
else | |
System.out.println("No"); | |
int [] array1 = {10, 34, 19, 27, 58, 45}; | |
if( hasSum(array1, 100) ) | |
System.out.println("Yes"); | |
else | |
System.out.println("No"); | |
} | |
//Brute force method based on recursion; exponential time cmplexity | |
/*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]); | |
}*/ | |
//method based on dynamic programming | |
public static boolean hasSum(int [] array, int sum) | |
{ | |
int len = array.length; | |
boolean[][] table = new boolean[sum+1][len+1]; | |
int i; | |
//If sum is zero; empty subset always has a sum 0; hence true | |
for( i = 0; i <= len; i++ ) | |
table[0][i] = true; | |
//If set is empty; no way to find the subset with non zero sum; hence false | |
for( i = 1; i <= sum; i++ ) | |
table[i][0] = false; | |
//calculate the table entries in terms of previous values | |
for( i = 1; i <= sum; i++ ) | |
{ | |
for( int j = 1; j <= len; j++ ) | |
{ | |
table[i][j] = table[i][j-1]; | |
if( !table[i][j] && i >= array[j-1] ) | |
table[i][j] = table[i-array[j-1]][j-1]; | |
} | |
} | |
return table[sum][len]; | |
} | |
} |