Dynamic Programming — Subset Sum Problem

Subset Sum Problem using DP in Java

So, if you have read my previous post on the Knapsack problem, the Subset Sum Problem is a variation of the 0/1 Knapsack problem.

It states something like this:

Given an array of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Example 1:
Input:
N = 6
arr[] = {3, 34, 4, 12, 5, 2}
sum = 9
Output: true
Explanation: Here there exists a subset with
sum = 9, 4+3+2 = 9.
Example 2: 
Input:
N = 6
arr[] = {3, 34, 4, 12, 5, 2}
sum = 30
Output: false
Explanation: There is no subset with sum 30.

So as with every DP problem, Let’s first try to build a recursive solution here. Unlink Knapsack, Here we don’t have a value array, so we can ignore that, and consider the input array as a weight array of the knapsack. And here all we need to check is if there exists such subset i.e. boolean value, unlike maximum profit from Knapsack. Now same as knapsack, We have two scenarios for each element:

• Its value is larger than the given sum.
• Its value is less than or equal to the given sum.

For the first case, We can’t include that element as part of the subset, because its value is more than the required sum of the subset.

For the second case, We have to decide if we should include this element in the subset or not. That basically means including this element will result in subset-sum being equal to the sum or excluding this element will result in subset-sum being equal to the sum. So we need to check both choices for the second case and pick whichever results in true i.e. giving us the subset-sum of the sum amount.

Here’s the recursive solution for it —

boolean isSubsetSumRecursive(int N, int arr[], int sum) {
             
    // Base case. 
    if (N==0 && sum==0) {return true;} // if both are empty, then true.
    if (N==0) {return false;} // If sum is not empty but no elements available, then false. 
    if (sum==0) {return true;} //if N is not empty but sum is 0, then empty subset will work, so true.
            
    //Taking N as index. 
    boolean isSubsetSum;
    
    //First case, we skip the element, because its large than sum.
    if (arr[N-1] > sum){ 
       isSubsetSum = isSubsetSumRecursive(N-1, arr, sum);
    } else {
    // Second case, We check with both cases if including or skipping, whichever results in making the isSubsetSum true. 
      isSubsetSum = isSubsetSumRecursive(N-1, arr, sum - arr[N-1]) || isSubsetSumRecursive(N-1, arr, sum);
    }
            
    return isSubsetSum;
}

In summary, This is the approach for solution here:
Two scenarios:
— element i is greater than Sum.
— element i is less or equal to Sum.

Case for first scenario:
— We can’t pick it in subset as its larger than the needed total Sum of subset.

Two cases for second scenario:
— Either we pick the element in subset.
— OR We don’t pick the element to be part of subset.

As we see multiple recursive calls being made in the above recursive solution with varying input values N and sum. So that implies there are overlapping recursive calls exist and we can utilize a top-down approach for optimizing this. Let’s create the table of size (N+1)*(sum+1), and use memoization to store the computed results of multiple recursive calls. See the code below -

static Boolean isSubsetSum(int N, int arr[], int sum){
boolean [][]t = new boolean[N+1][sum+1];
        
// Default case: 
  - if numbers count is 0 and 0 sum is needed. Then empty subset will work fine, so thats true. (i==0 && j==0)
  - If required sum is not zero, but count is zero, then false, because we need non empty subset to make the summation but no numbers are available or numbers count is zero, hence false.(i==0)
  - If required sum is zero, so its true. We can return empty subset even if numbers count is not zero, so that's true.(j==0)
for (int i=0; i<N+1; i++) {// Numbers
            for (int j=0; j<sum+1; j++) { // Sum. 
                if (i==0 && j==0) {
                    t[i][j] = true;
                } else if (i==0) {
                    t[i][j] = false;
                } else if (j==0) {
                    t[i][j] = true;
                }
                
            }
        }
        
        for (int i=1; i<N+1; i++) { // items 
            for (int j=1; j<sum+1; j++) { // sum
                
                if (arr[i-1] > j) { // item's value is large than the current sum, skipping it. Checking over remaining input i-1 with same sum value j. 
                    t[i][j] = t[i-1][j];
                } else { // item's value is less than current sum, making choice between taking or skipping. if including then check over remaining input i-1 with sum value (j - current element's value), if excluding check over remaining input i-1 with same sum value j. So like in Knapsack, We used to check for maximum profit so we used to consider max of both values, here we are checking existance of such subset, so we are considering boolean result and hence taking an OR of both choices result. 
                    t[i][j] = t[i-1][j-arr[i-1]] || t[i-1][j]; // taking || skipping.
                }
                
            }
        }
        
        return t[N][sum]; 
}

Our sum will be stored at t[N][sum]. The answer from all possible subproblems will be finally stored at t[N][sum] for the subset from N elements array having subset-sum equal to the sum. See How easy is it if you are already aware of knapsack problem and solution, and even if you aren’t, it's not difficult.

Thanks for reading it up till here. Let me know any suggestions, notes, or opinions in the comments. Those are highly welcomed.