Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
APPROACH 1
3.1.
Implementation in C++
3.2.
Complexity Analysis
4.
APPROACH 2
4.1.
Implementation in C++
4.2.
Complexity Analysis
5.
APPROACH 3
5.1.
Implementation in C++
5.2.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
What optimization did we do on the recursive approach for the Subset Sum problem?
6.2.
What is the time complexity for the optimized approach?
6.3.
Can we apply a similar approach if both the array length and the target value have their maximum value of 10⁵?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Subset Sum Problem

Author Nishant Rana
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

(Must Read: Data Structure)

Problem Statement

You are given an array of non-negative integers and an integer value ‘target’. You need to search if there is a subset whose sum is equal to ‘target’.

Let us see a few examples: 

Example 1

Input: 

arr: {1, 2, 3, 4, 5}

target: 10

Output: True

Explanation: 

{1, 4, 5} is one of the subsets of the input array whose subset-sum is equal to the target value i.e., 10.

 

Example 2

Input: 

arr: {3, 7, 12, 2, 5}

target: 11

Output: False

Explanation: 

There is no subset whose subset-sum is equal to the given target value.

Recommended: Try the Problem yourself before moving on to the solution

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

APPROACH 1

We can use Recursion here to solve this problem.

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.

recursion 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.

Refer to the below implementation for the above optimization. (Also see Dynamic Programming Algorithms)

Implementation in C++

#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.

We know your thirst for knowledge is never-ending so check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio. To practice this problem you can visit Practice Problem and even check out some similar problems such as Minimum Subset Sum Difference. Also, check out some Top Dynamic Programming Problems and an interesting article on Memonisation v/s Tabulation to keep you on your toes.

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Count Number of Subsets With Given Sum
Next article
Minimum insertion to convert the string to a palindrome
Live masterclass