Subset Sum 2 Editorial

Practice Problem Link: Practice Problem | Subset Sum 2

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a set A composed of non-negative integers, find if it has a subset with a sum equal to a given target.

Naive Approach

This problem can be solved by a brute force recursion. Notice, that when processing a subset, we have 2 choices, either take the current element or don’t take it. So, we can recursively check for the possibilities and return true if we find an appropriate subset, else return false.

Analysis

• Time Complexity: Exponential
• Space Complexity: O(1)

Implementation

C++

int checkSum(vector<int> &A, int n, int target) {
   if(target == 0) {
       return 1;
   }
   if(n == 0) {
       return 0;
   }
   if(A[n - 1] > target) {
       return checkSum(A, n - 1, target);
   }
   return checkSum(A, n - 1, target) || checkSum(A, n - 1, target - A[n - 1]);
}
int subsetSum(vector<int> &A, int target) {
   return checkSum(A, A.size(), target);
}

Java

class Solution {
   boolean checkSum(int[] A, int n, int target) {
       if(target == 0) {
           return true;
       }
       if(n == 0) {
           return false;
       }
       if(A[n - 1] > target) {
           return checkSum(A, n - 1, target);
       }
       return checkSum(A, n - 1, target) || checkSum(A, n - 1, target - A[n - 1]);
   }
   int subsetSum(int[] A, int target) {
       return checkSum(A, A.length, target) ? 1 : 0;
   }
}

Optimal Approach

We can observe that in our naive approach, multiple recursion calls are the same and are being redundantly recalculated. So, we can memoize those recursive calls using Dynamic Programming, to optimize our time complexity.

DP[i][j] will represent if it is possible to attain a subset made of the 1st i elements in the array, which adds up to sum j.

Analysis

• Time Complexity: O(n * target)
• Space Complexity: O(n * target)

Implementation

C++

vector<vector<int>> dp;
int checkSum(vector<int> &A, int n, int target) {
   if(target == 0) {
       return 1;
   }
   if(n == 0) {
       return 0;
   }
   if(dp[n][target] != -1){
       return dp[n][target];
   }
   if(A[n - 1] > target) {
       return dp[n][target] = checkSum(A, n - 1, target);
   }
   return dp[n][target] = checkSum(A, n - 1, target) || checkSum(A, n - 1, target - A[n - 1]);
}
int subsetSum(vector<int> &A, int target) {
   vector<vector<int>> temp(A.size() + 1, vector<int> (target + 1, -1));
   dp = temp;
   return checkSum(A, A.size(), target);
}

Java

class Solution {
   int dp[][];
   boolean checkSum(int[] A, int n, int target) {
       if(target == 0) {
           return true;
       }
       if(n == 0) {
           return false;
       }
       if(dp[n][target] != -1) {
           return dp[n][target] == 1 ? true : false;
       }
       if(A[n - 1] > target) {
           dp[n][target] = checkSum(A, n - 1, target) ? 1 : 0;
           return dp[n][target] == 1 ? true : false;
       }
       dp[n][target] = (checkSum(A, n - 1, target) || checkSum(A, n - 1, target - A[n - 1])) ? 1 : 0;
       return (dp[n][target] == 1 ? true : false);
   }
   int subsetSum(int[] A, int target) {
       dp = new int[A.length + 1][target + 1];
       for(int i = 0; i <= A.length; i++) {
           for(int j = 0; j <= target; j++) {
               dp[i][j] = -1;
           }
       }
       return checkSum(A, A.length, target) ? 1 : 0;
   }
}

Implementation (Bottom-up)

C++

int subsetSum(vector<int> &A, int target) {
   int n = A.size();
   bool dp[n + 1][target + 1];
   for(int i = 0; i <= n; i++) {
       for(int j = 0; j <= target; j++) {
           if(i == 0 && j != 0) {
               dp[i][j] = false;
           } else if(j == 0) {
               dp[i][j] = true;
           } else {
               if(j - A[i - 1] >= 0) {
                   dp[i][j] = dp[i - 1][j - A[i - 1]] || dp[i - 1[j];
               } else {
                   dp[i][j] = dp[i - 1][j];
               }
           }
       }
   }
   return dp[n][target];
}

Java

class Solution {
   int subsetSum(int[] A, int target) {
       boolean[][] dp = new boolean[A.length + 1][target + 1];
       for(int i = 0; i <= A.length; i++) {
           for(int j = 0; j <= target; j++) {
               if(j == 0) {
                   dp[i][j] = true;
               } else if(i == 0) {
                   dp[i][j] = false;
               } else {
                   if(j - A[i - 1] >= 0) {
                       dp[i][j] = dp[i - 1][j - A[i - 1]] || dp[i - 1][j];
                   } else {
                       dp[i][j] = dp[i - 1][j];
                   }
               }
           }
       }
       return dp[A.length][target] ? 1 : 0;
   }
}