Home » Interview coding problems/challenges

Subset Sum Problem

Subset Sum Problem: Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with a sum equal to the given sum.
Submitted by Divyansh Jaipuriyar, on April 10, 2021

Description: The problem has been featured in interview/coding rounds of many top tech companies such as Amazon, Samsung, etc.

Problem Statement: Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with a sum equal to the given sum.

Problem Description: Given problem asks you to check whether it is possible to get a subset whose sum is equal to the given sum as in the question if possible you are asked to print "YES" otherwise print "NO".

Input: The first line contains an integer 'T' denoting the total number of test cases. Each test case constitutes two lines. The first line contains 'N', representing the number of elements in the set and the second line contains the elements of the set.

Output: Print "YES" if there is a subset with a sum equal to the given number and "NO" if there is no subset is present.

Example:

Input:
T = 1
N = 7
[5,6,7,8,9,10,11]
sum = 19

Output:
"YES"
{5,6,8}, {11,8}, {10,9} are possible subset with the sum 
of elements of the subset equal to given sum as 19.

Input:
T = 1
N = 3
[5,6,7]
sum = 4

Output:
"NO",
no subset is possible since there is no subset 
which has sum equal to given sum=4.

Solution Approach

(a) Recursion Approach

In this case, we will consider two possibilities as, we consider the last element and decrease the required sum by that element i.e., required sum=required sum-last element value, array size=array size-1; another case is that we totally neglect the last element's value and decrease the size of the array by one.

required sum=required sum, array size =array size-1;

One more case, if the last element's value is greater than the sum then simply decreases the size of the array by one.

The following steps are used:

1. We create a solve function that will take three parameters as arr, index position, and required sum.
2. Each time we check if the required sum is zero or not, if the sum is zero then we return true since an empty subset is always possible for some element.
3. If sum is not zero then we check if the array index is under the correct bound or not it does not then return false since it is not possible.
4. We then check the value of the array element if it is greater than sum then also, we cannot include it in our subset-sum.
5. Otherwise, we have two possibilities as we either include it or not include it in our subset.

Time Complexity for the above approach is exponential.

Code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

bool solve(ll arr[], ll n, ll sum)
{
    //if required sum is zero then its case of empty subset.
    if (sum == 0)
        return true;
    //if size of array is 0 and required sum is not zero then return false.
    else if (n == 0 and sum != 0)
        return false;
    //if last element value is greater than sum then call solve function
    //for rest elements excluding last element.
    else if (arr[n - 1] > sum)
        return (solve(arr, n - 1, sum));
    else
        //call solve function for rest of the cases.
        return (solve(arr, n - 1, sum) || solve(arr, n - 1, sum - arr[n - 1]));
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;

        ll arr[n];
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        ll sum;
        cout << "Enter sum: ";
        cin >> sum;

        bool res = solve(arr, n, sum);
        if (res)
            cout << "YES"
                 << "\n";
        else
            cout << "NO"
                 << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 5
Enter elements: 1 2 3 4 5
Enter sum: 7
YES
Enter size of array: 4
Enter elements: 5 6 7 8
Enter sum: 3
NO
Enter size of array: 3        
Enter elements: 11 22 33
Enter sum: 35
NO

(b) Dynamic Programming Approach

(i) Top-Down Approach:

Here, we will use the memorization method, we will use dp[n][sum] as our dp state, where n is the number of elements and sum is the required sum, we will initialize all the dp[n][sum] as -1 and whenever we get dp[n][sum] as !=-1 we simply return it from the table of dp[n][sum] without recalculating it again and again.

Following steps are used in top-dp:

1. First, we create a dp[][] state which will depend on two values as an index and the sum so dp[i][j], where i is the index value and j is the sum value.
2. Initially, all the dp[][] state are filled with -1, and each time we make the recursive call we first check it on dp[][] table if calculated then we simply return it otherwise we calculate it.
3. All the condition for top-down dp[][] depends same as the recursive approach except that we use memorization technique in top-down which we exclude it in recursive approach.

Time Complexity for the above approach is: O(n*n)

Space Complexity for the above approach is: O(n*n)

Code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dp[1003][1003];

bool solve(ll arr[], ll n, ll sum)
{
    //if required sum is zero then its case of empty subset.
    if (sum == 0)
        return (dp[n][sum] = true);
    //if size of array is 0 and required sum is not zero then return false.
    else if (n == 0 and sum != 0)
        return (dp[n][sum] = false);

    //if the dp[n][sum] is already calculated then simply return
    //the value without calculating it again.
    if (dp[n][sum] != -1)
        return dp[n][sum];
    //if last element value is greater than sum then call solve
    //function for rest elements excluding last element.
    else if (arr[n - 1] > sum)
        return (dp[n][sum] = (solve(arr, n - 1, sum)));
    else
        //call solve function for rest of the cases.
        return (dp[n][sum] = (solve(arr, n - 1, sum) || solve(arr, n - 1, sum - arr[n - 1])));
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;

        ll arr[n];
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        memset(dp, -1, sizeof(dp));

        ll sum;
        cout << "Enter sum: ";
        cin >> sum;

        bool res = solve(arr, n, sum);
        if (res)
            cout << "YES"
                 << "\n";
        else
            cout << "NO"
                 << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 5
Enter elements: 5 6 7 8 9
Enter sum: 13
YES
Enter size of array: 6
Enter elements: 6 7 8 9 10 12
Enter sum: 4
NO
Enter size of array: 5        
Enter elements: 6 5 9 6 7
Enter sum: 16
YES

(ii) Bottom-Up Approach

In this case, we fill the table in a bottom-up manner, we will use dp[n][sum] as our dp state where n is the number of elements in the array and sum is the required sum.

Following are the base cases:

• if sum==0 then dp[i][0]=true
• if n==0 and sum !=0 then dp[0][i]=false

Follow steps are used in bottom-up dp for this problem:

1. We first create dp[n+1][sum+1] state as indexing start from 0.
2. For cases where our required sum is zero and the element are in a valid index range then we make dp[i][0]=true since an empty subset is always possible.
3. For cases where we have index 0 then we cannot make any subset since we don't have any element.
4. We also need to check if the required sum j is greater than the array element at index i or not if not then we simply ignore it otherwise we have two possibilities of including and excluding.
5. Finally, we return the last element of the dp[n+1][sum+1] that is dp[n][sum] value which is formed with the help of n element and required sum.

Time Complexity for the above approach is: O(n*n)

space complexity for the above approach is: O(n*n)

Code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;

        ll arr[n];
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        ll sum;
        cout << "Enter sum: ";
        cin >> sum;

        ll dp[n + 1][sum + 1]; //declare dp array.

        //initialise base cases when sum==0 and n!=0
        for (ll i = 0; i <= n; i++)
            dp[i][0] = true;
        //initialise base cases when sum!=0 and n==0
        for (ll i = 1; i <= sum; i++)
            dp[0][i] = false;

        //fill table in bottom up manner.
        for (ll i = 1; i <= n; i++)
            for (ll j = 1; j <= sum; j++) {
                //if required sum>=array's element check for both possibilities.
                if (j >= arr[i - 1])
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
                else
                    //array's value is greater than required sum then ignore it
                    //and consider of remaining cases.
                    dp[i][j] = dp[i - 1][j];
            }
        if (dp[n][sum])
            cout << "YES"
                 << "\n";
        else
            cout << "NO"
                 << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 3
Enter elements: 4 5 6
Enter sum: 9
YES
Enter size of array: 3
Enter elements: 7 5 9
Enter sum: 6
NO
Enter size of array: 5
Enter elements: 5 5 5 5 5
Enter sum: 36
NO