Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
Subset Sum is one of the most popular problems that is asked in interviews. It sounds like it might be a big deal but the problem is actually fairly straightforward and simple. We are provided with an array of integers and a target sum.
We have to determine whether there is a subset of the array present in such a manner that the sum of all the elements in that subset is equal to that of the target value provided. Sounds simple right? Let's get right to the problem then.
We can use the pick and non-pick strategy here to search for a subset whose sum is equal to the given target value. We can start from the ‘i’ = 0 index and make two moves, either picking the current element or leaving the current element.
If you pick the current element, add its value to the sum variable you are maintaining for each recursive call else, don’t add and call the recursive function for the ‘i + 1th’ index. When your ‘i’ reaches the value ‘N’ ( where ‘N’ is the total number of elements in the array), just check if your sum is equal to the target value or not.
Refer to the below recursive tree.
Do refer to the below implementation of the above approach.
Implementation
C++
Java
C#
Python
JavaScript
C++
#include <iostream> using namespace std;
/* Returns true if there is a subset of input arr with subset sum equal to given sum */ bool isSubsetSum(int arr[], int i, int sum, int target, int n) {
// Base Cases if(i == n){ return sum == target; } if (sum > target){ return false; } if (sum == target){ return true; }
/* Applying the pick and non-pick approach. We will try both the cases to include or not include the current element in the subset sum. */ return isSubsetSum(arr, i + 1, sum, target, n) || isSubsetSum(arr, i + 1, sum + arr[i], target, n); }
// Driver code int main() { int arr[] = {1, 2, 3, 4, 5}; int target = 50; int n = sizeof(arr) / sizeof(arr[0]);
if (isSubsetSum(arr, 0, 0, target, n) == true){ cout <<"Found a subset with given sum"; } else{ cout <<"No subset with given sum"; } return 0; }
You can also try this code with Online C++ Compiler
static boolean isSubsetSum(int[] arr, int i, int sum, int target, int n) { // Base Cases if (i == n) { return sum == target; } if (sum > target) { return false; } if (sum == target) { return true; }
// Pick or non-pick approach return isSubsetSum(arr, i + 1, sum, target, n) || isSubsetSum(arr, i + 1, sum + arr[i], target, n); }
public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5}; int target = 50; int n = arr.length;
if (isSubsetSum(arr, 0, 0, target, n)) { System.out.println("Found a subset with given sum"); } else { System.out.println("No subset with given sum"); } } }
You can also try this code with Online Java Compiler
static bool IsSubsetSum(int[] arr, int i, int sum, int target, int n) { // Base Cases if (i == n) { return sum == target; } if (sum > target) { return false; } if (sum == target) { return true; }
// Pick or non-pick approach return IsSubsetSum(arr, i + 1, sum, target, n) || IsSubsetSum(arr, i + 1, sum + arr[i], target, n); }
public static void Main() { int[] arr = {1, 2, 3, 4, 5}; int target = 50; int n = arr.Length;
if (IsSubsetSum(arr, 0, 0, target, n)) { Console.WriteLine("Found a subset with given sum"); } else { Console.WriteLine("No subset with given sum"); } } }
Python
def is_subset_sum(arr, i, sum, target, n): # Base Cases if i == n: return sum == target if sum > target: return False if sum == target: return True
# Pick or non-pick approach return is_subset_sum(arr, i + 1, sum, target, n) or \ is_subset_sum(arr, i + 1, sum + arr[i], target, n)
function isSubsetSum(arr, i, sum, target, n) { // Base Cases if (i === n) { return sum === target; } if (sum > target) { return false; } if (sum === target) { return true; }
// Pick or non-pick approach return isSubsetSum(arr, i + 1, sum, target, n) || isSubsetSum(arr, i + 1, sum + arr[i], target, n); }
Time Complexity: The time complexity for the approach is 2ⁿ because for each element we are making two decisions either to pick the current element or not to pick the current element.
Space Complexity: The space complexity for the above approach is constant. We are not using any auxiliary space.
Approach 2
We can optimize APPROACH 1 by memoizing it. We can create a 2D Dynamic Programming table of size (arr.size() + 1) * (target + 1) to store the answer for each ‘i’ and ‘sum’ value because it might be possible that we try to compute the answer for the same ‘i’ and ‘sum’ values.
/* Returns true if there is a subset of input arr with subset sum equal to given sum */ int isSubsetSum(int arr[], int i, int sum, int target, int n) {
// Base Cases if(i == n){ return sum == target; } if (sum > target){ return 0; } if (sum == target){ return 1; }
/* If the answer for current state is already present. */ if(dp[i][sum] != -1){ return dp[i][sum]; }
/* Applying the pick and non-pick approach. We will try both the cases to include or not include the current element in our subset sum. */ return dp[i][sum] = isSubsetSum(arr, i + 1, sum, target, n) || isSubsetSum(arr, i + 1, sum + arr[i], target, n); }
// Driver code int main() { int arr[] = {1, 2, 3, 4, 5}; int target = 10; int n = sizeof(arr) / sizeof(arr[0]);
// Storing the value -1 to the dp table memset(dp, -1, sizeof(dp));
if (isSubsetSum(arr, 0, 0, target, n)){ cout <<"Found a subset with given sum"; } else{ cout <<"No subset with given sum"; } return 0; }
You can also try this code with Online C++ Compiler
static boolean isSubsetSum(int[] arr, int i, int sum, int target, int n) { // Base Cases if (i == n) { return sum == target; } if (sum > target) { return false; } if (sum == target) { return true; }
// Pick or non-pick approach boolean result = isSubsetSum(arr, i + 1, sum, target, n) || isSubsetSum(arr, i + 1, sum + arr[i], target, n);
dp[i][sum] = result ? 1 : 0; return result; }
public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5}; int target = 10; int n = arr.length;
// Initialize dp table with -1 for (int[] row : dp) { Arrays.fill(row, -1); }
if (isSubsetSum(arr, 0, 0, target, n)) { System.out.println("Found a subset with given sum"); } else { System.out.println("No subset with given sum"); } } }
You can also try this code with Online Java Compiler
static bool IsSubsetSum(int[] arr, int i, int sum, int target, int n) { // Base Cases if (i == n) { return sum == target; } if (sum > target) { return false; } if (sum == target) { return true; }
// Pick or non-pick approach bool result = IsSubsetSum(arr, i + 1, sum, target, n) || IsSubsetSum(arr, i + 1, sum + arr[i], target, n);
dp[i, sum] = result ? 1 : 0; return result; }
public static void Main() { int[] arr = {1, 2, 3, 4, 5}; int target = 10; int n = arr.Length;
// Initialize dp table with -1 for (int j = 0; j < dp.GetLength(0); j++) for (int k = 0; k < dp.GetLength(1); k++) dp[j, k] = -1;
if (IsSubsetSum(arr, 0, 0, target, n)) { Console.WriteLine("Found a subset with given sum"); } else { Console.WriteLine("No subset with given sum"); } } }
Python
dp = [[-1 for _ in range(2000)] for _ in range(2000)]
def is_subset_sum(arr, i, sum, target, n): # Base Cases if i == n: return sum == target if sum > target: return False if sum == target: return True
function isSubsetSum(arr, i, sum, target, n) { // Base Cases if (i === n) { return sum === target; } if (sum > target) { return false; } if (sum === target) { return true; }
Time Complexity: The time complexity for the above approach is (arr.size() + 1) * (target + 1) because we are storing the answer for all possible ‘i’ and ‘sum’ pairs, and if we have already calculated the answer for any recursion call we return its answer stores in the DP table.
Space Complexity: The space complexity for the above approach is (arr.size() + 1) * (target + 1) because we are creating a DP table of size (arr.size() + 1) * (target + 1) to store the answer for different ‘i’ and ‘sum’ pairs.
Approach 3
We can solve the above recursive approach in an iterative manner using bottom-up D.P.
We can create a 2D D.P. similar to the second approach of size (target + 1) * (arr.size() + 1) to store the answer for each ‘i’ and ‘sum’ values.
Implementation
C++
Java
C#
Python
JavaScript
C++
#include <iostream> using namespace std;
/* Returns true if there is a subset of a[] with sum equal to given sum */ bool isSubsetSum(int a[], int n, int sum) {
/* The value of dp[i][j] will be true if there is a subset of a[0..j-1] with sum equal to i */ bool dp[n + 1][sum + 1];
// If sum is 0, then answer is true for (int i = 0; i <= n; i++) dp[0][i] = true;
/* If sum is not 0 and set is empty, then answer is false */ for (int i = 1; i <= sum; i++) dp[i][0] = false;
/* Fill the dp table in bottom up manner */ for (int i = 1; i <= sum; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i][j - 1]; if (i >= a[j - 1]){ dp[i][j] = dp[i][j] || dp[i - a[j - 1]][j - 1]; } } }
return dp[sum][n]; }
int main() { int a[] = { 1, 2, 3, 4, 5 }; int sum = 7; int n = sizeof(a) / sizeof(a[0]);
if (isSubsetSum(a, n, sum) == true){ cout <<"Found a subset with given sum"; } else{ cout <<"No subset with given sum"; } return 0; }
You can also try this code with Online C++ Compiler
public static bool IsSubsetSum(int[] a, int n, int sum) { bool[,] dp = new bool[sum + 1, n + 1];
// If sum is 0, answer is true for (int i = 0; i <= n; i++) { dp[0, i] = true; }
// If sum is not 0 and set is empty, answer is false for (int i = 1; i <= sum; i++) { dp[i, 0] = false; }
// Fill dp table in bottom-up manner for (int i = 1; i <= sum; i++) { for (int j = 1; j <= n; j++) { dp[i, j] = dp[i, j - 1]; if (i >= a[j - 1]) { dp[i, j] = dp[i, j] || dp[i - a[j - 1], j - 1]; } } }
return dp[sum, n]; }
public static void Main() { int[] a = {1, 2, 3, 4, 5}; int sum = 7; int n = a.Length;
if (IsSubsetSum(a, n, sum)) { Console.WriteLine("Found a subset with given sum"); } else { Console.WriteLine("No subset with given sum"); } } }
Python
def is_subset_sum(a, n, sum): dp = [[False] * (n + 1) for _ in range(sum + 1)]
# If sum is 0, answer is true for i in range(n + 1): dp[0][i] = True
# If sum is not 0 and set is empty, answer is false for i in range(1, sum + 1): dp[i][0] = False
# Fill dp table in bottom-up manner for i in range(1, sum + 1): for j in range(1, n + 1): dp[i][j] = dp[i][j - 1] if i >= a[j - 1]: dp[i][j] = dp[i][j] or dp[i - a[j - 1]][j - 1]
return dp[sum][n]
# Driver code a = [1, 2, 3, 4, 5] sum_value = 7 n = len(a)
if is_subset_sum(a, n, sum_value): print("Found a subset with given sum") else: print("No subset with given sum")
You can also try this code with Online Python Compiler
Time Complexity: The time complexity for the above approach is (arr.size() + 1) * (target + 1) because we are storing the answer for all possible ‘i’ and ‘sum’ pairs.
Space Complexity: The space complexity for the above approach is (arr.size() + 1) * (target + 1) because we are creating a DP table of size (arr.size() + 1) * (target + 1) to store the answer for different ‘i’ and ‘sum’ pairs.
To better understand and implement the code, check out this video for both the recursive and dynamic programming solutions.
Frequently Asked Questions
What optimization did we do on the recursive approach for the Subset Sum problem?
Since we were computing the answer for the same state at different times, we made a DP table to store the answer for the states we already computed, so that if in the future we need the answer for that state we can directly return the answer from the DP table.
What is the difference between the Subset Sum Problem and the Partition Problem?
The Subset Sum Problem checks if any subset of a set can sum to a target value, while the Partition Problem determines if a set can be divided into two subsets with equal sums. Partition is a special case of subset sum with target as half of the total sum.
What are the common strategies to solve the Sum of Subset Problem?
Common strategies to solve the Subset Sum Problem include dynamic programming (bottom-up and top-down approaches), backtracking for exploring subsets, and memoization to optimize repeated computations.
Can the Sum of Subset Problem be solved using greedy algorithms?
The Subset Sum Problem cannot be solved using greedy algorithms, as they do not guarantee finding an optimal solution for all subsets. Greedy choices may overlook feasible subsets that satisfy the required sum.
Conclusion
In this blog, we explored the popular Subset Sum Problem. We started with the basic brute-force approach using recursion, then advanced to an optimal solution utilizing Dynamic Programming for efficiency. We know your thirst for knowledge is endless, so keep learning and exploring!