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 in 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;
}

OUTPUT

Found a subset with given sum

Complexity Analysis

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.

#include <bits/stdc++.h>
using namespace std;
//Making the dp table global
int dp[2000][2000];
/*
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;
}

OUTPUT

Found a subset with given sum

Complexity Analysis

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 in 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;
}

OUTPUT

Found a subset with given sum

Complexity Analysis

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 time complexity for the optimized approach?

The time complexity for the optimized 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.

Can we apply a similar approach if both the array length and the target value have their maximum value of 10⁵?

No, if we apply a similar approach for the mentioned constraints, the compiler will give us the ‘Memory Limit Exceeded’ error because of forming the DP table.

Conclusion

In this blog, we have covered the popular subset sum problem. We first saw the less efficient brute force method to solve the problem using recursion and then moved on to an optimal solution that involved the use of the concepts of Dynamic Programming.