Java Program for Subset Sum Problem | DP-25
Write a Java program for a given set of non-negative integers and a value sum, the task is to check if there is a subset of the given set whose sum is equal to the given sum.
Examples:
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
Explanation: There is a subset (4, 5) with sum 9.Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
Explanation: There is no subset that adds up to 30.
Java Program for Subset Sum Problem using Recursion:
For the recursive approach, there will be two cases.
- Consider the ‘last’ element to be a part of the subset. Now the new required sum = required sum – value of ‘last’ element.
- Don’t include the ‘last’ element in the subset. Then the new required sum = old required sum.
In both cases, the number of available elements decreases by 1.
Step-by-step approach:
- Build a recursive function and pass the index to be considered (here gradually moving from the last end) and the remaining sum amount.
- For each index check the base cases and utilize the above recursive call.
- If the answer is true for any recursion call, then there exists such a subset. Otherwise, no such subset exists.
Below is the implementation of the above approach.
Java
// A recursive solution for subset sum import java.io.*; class GFG { // Returns true if there is a subset // of set[] with sum equal to given sum static boolean isSubsetSum( int set[], int n, int sum) { // Base Cases if (sum == 0 ) return true ; if (n == 0 ) return false ; // If last element is greater than // sum, then ignore it if (set[n - 1 ] > sum) return isSubsetSum(set, n - 1 , sum); // Else, check if sum can be obtained // by any of the following // (a) including the last element // (b) excluding the last element return isSubsetSum(set, n - 1 , sum) || isSubsetSum(set, n - 1 , sum - set[n - 1 ]); } // Driver code public static void main(String args[]) { int set[] = { 3 , 34 , 4 , 12 , 5 , 2 }; int sum = 9 ; int n = set.length; if (isSubsetSum(set, n, sum) == true ) System.out.println( "Found a subset" + " with given sum" ); else System.out.println( "No subset with" + " given sum" ); } } /* This code is contributed by Rajat Mishra */ |
Found a subset with given sum
Time Complexity: O(2n)
Auxiliary space: O(n)
Java Program for Subset Sum Problem using Memoization:
As seen in the previous recursion method, each state of the solution can be uniquely identified using two variables – the index and the remaining sum. So create a 2D array to store the value of each state to avoid recalculation of the same state.
Below is the implementation of the above approach:
Java
// Java program for the above approach import java.io.*; class GFG { // Check if possible subset with // given sum is possible or not static int subsetSum( int a[], int n, int sum) { // Storing the value -1 to the matrix int tab[][] = new int [n + 1 ][sum + 1 ]; for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= sum; j++) { tab[i][j] = - 1 ; } } // If the sum is zero it means // we got our expected sum if (sum == 0 ) return 1 ; if (n <= 0 ) return 0 ; // If the value is not -1 it means it // already call the function // with the same value. // it will save our from the repetition. if (tab[n - 1 ][sum] != - 1 ) return tab[n - 1 ][sum]; // If the value of a[n-1] is // greater than the sum. // we call for the next value if (a[n - 1 ] > sum) return tab[n - 1 ][sum] = subsetSum(a, n - 1 , sum); else { // Here we do two calls because we // don't know which value is // full-fill our criteria // that's why we doing two calls if (subsetSum(a, n - 1 , sum) != 0 || subsetSum(a, n - 1 , sum - a[n - 1 ]) != 0 ) { return tab[n - 1 ][sum] = 1 ; } else return tab[n - 1 ][sum] = 0 ; } } // Driver Code public static void main(String[] args) { int n = 5 ; int a[] = { 1 , 5 , 3 , 7 , 4 }; int sum = 12 ; if (subsetSum(a, n, sum) != 0 ) { System.out.println( "YES\n" ); } else System.out.println( "NO\n" ); } } // This code is contributed by rajsanghavi9. |
YES
Time Complexity: O(sum*n)
Auxiliary space: O(n)
Java Program for Subset Sum Problem using Dynamic Programming:
We can solve the problem in Pseudo-polynomial time we can use the Dynamic programming approach.
So we will create a 2D array of size (n + 1) * (sum + 1) of type boolean. The state dp[i][j] will be true if there exists a subset of elements from set[0 . . . i] with sum value = ‘j’.
The dynamic programming relation is as follows:
if (A[i-1] > j)
dp[i][j] = dp[i-1][j]
else
dp[i][j] = dp[i-1][j] OR dp[i-1][j-set[i-1]]
Below is the implementation of the above approach:
Java
// A Dynamic Programming solution for subset // sum problem import java.io.*; class GFG { // Returns true if there is a subset of // set[] with sum equal to given sum static boolean isSubsetSum( int set[], int n, int sum) { // The value of subset[i][j] will be // true if there is a subset of // set[0..j-1] with sum equal to i boolean subset[][] = new boolean [sum + 1 ][n + 1 ]; // If sum is 0, then answer is true for ( int i = 0 ; i <= n; i++) subset[ 0 ][i] = true ; // If sum is not 0 and set is empty, // then answer is false for ( int i = 1 ; i <= sum; i++) subset[i][ 0 ] = false ; // Fill the subset table in bottom // up manner for ( int i = 1 ; i <= sum; i++) { for ( int j = 1 ; j <= n; j++) { subset[i][j] = subset[i][j - 1 ]; if (i >= set[j - 1 ]) subset[i][j] = subset[i][j] || subset[i - set[j - 1 ]][j - 1 ]; } } return subset[sum][n]; } // Driver code public static void main(String args[]) { int set[] = { 3 , 34 , 4 , 12 , 5 , 2 }; int sum = 9 ; int n = set.length; if (isSubsetSum(set, n, sum) == true ) System.out.println( "Found a subset" + " with given sum" ); else System.out.println( "No subset with" + " given sum" ); } } /* This code is contributed by Rajat Mishra */ |
Found a subset with given sum
Time Complexity: O(sum * n), where n is the size of the array.
Auxiliary Space: O(sum*n), as the size of the 2-D array is sum*n.
Java Program for Subset Sum Problem using Dynamic Programming with space optimization to linear:
In previous approach of dynamic programming we have derive the relation between states as given below:
if (A[i-1] > j)
dp[i][j] = dp[i-1][j]
else
dp[i][j] = dp[i-1][j] OR dp[i-1][j-set[i-1]]
If we observe that for calculating current dp[i][j] state we only need previous row dp[i-1][j] or dp[i-1][j-set[i-1]].
There is no need to store all the previous states just one previous state is used to compute result.
Step-by-step approach:
- Define two arrays prev and curr of size Sum+1 to store the just previous row result and current row result respectively.
- Once curr array is calculated then curr becomes our prev for the next row.
- When all rows are processed the answer is stored in prev array.
Below is the implementation of the above approach:
Java
import java.util.Arrays; public class SubsetSum { public static boolean isSubsetSum( int [] set, int n, int sum) { boolean [] prev = new boolean [sum + 1 ]; Arrays.fill(prev, false ); for ( int i = 0 ; i <= n; i++) { prev[ 0 ] = true ; } boolean [] curr = new boolean [sum + 1 ]; for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= sum; j++) { if (j < set[i - 1 ]) { curr[j] = prev[j]; } if (j >= set[i - 1 ]) { curr[j] = prev[j] || prev[j - set[i - 1 ]]; } } // Now curr becomes prev for (i + 1)th element System.arraycopy(curr, 0 , prev, 0 , sum + 1 ); } return prev[sum]; } public static void main(String[] args) { int [] set = { 3 , 34 , 4 , 12 , 5 , 2 }; int sum = 9 ; int n = set.length; if (isSubsetSum(set, n, sum)) { System.out.println( "Found a subset with given sum" ); } else { System.out.println( "No subset with given sum" ); } } } |
Found a subset with given sum
Time Complexity: O(sum * n), where n is the size of the array.
Auxiliary Space: O(sum), as the size of the 1-D array is sum+1.
Please refer complete article on Subset Sum Problem | DP-25 for more details!