Home » Interview coding problems/challenges

Subset Sum

Subset Sum: Here, we are going to learn how to solve the subset sum problem which has been featured in many interview rounds like Amazon, Microsoft? Submitted by Radib Kar, on February 29, 2020

Description

In this article, we are going to see how to solve the subset sum problem which has been featured in many interview rounds like Amazon, Microsoft?

Problem statement

Given an array of size n and a sum K, determine whether any subset is possible with that sum or not. Print "yes" if there is any subset present else print "no".

    Input & output:
    In the first line the input will be n and K, space separated.
    The next line contains the array elements

    Output will be "yes" or "no"

Explanation with example

Example 1:

    Input:

    The array size be: 5
    The sum be: 11
    The Elements be: 5 6 7 3 9

    Output:
    Yes

    Explanation:
    5 & 6 sums to 11. Thus the subset can be [5, 6] and output will be "yes".

Example 2:

    Input:

    The array size be: 5
    The sum be: 11
    The Elements be: 5 6 7 3 9

    Output:
    Yes

    Explanation:
    5 & 6 sums to 11. Thus the subset can be [5, 6] and output will be "yes".

Solution Approach

Of course the naïve solution would be to generate all possible subsets and check their sum equals to K or not. But it would of course be computationally exponential to generate all possible subsets.

To do so, the recursion would be:

For n_th element the cases are:

1. Consider the n^th element as part of solution subset and recur for n-1 elements for obtaining sum (K-arr[n]).
2. Don't consider n^th element as part of solution subset and recur for n-1 elements for obtaining sum (K).

So, the recursion function can be written as:

    f(n,K)=f(n-1,K) | f(n-1,K-arr[n-1])

Where,

    f(n,K)= value for problem with array size n and sum K which can be either true or false

Now base case would be,

    f(0,0) = true
    f(0,i) = false for 1 ≤ i ≤K
    f(i,0) = true 1 ≤ i ≤ n

Here comes the concept of sub problem. Initially the problem is for size n and sum K. Then it gets reduced to {size (n-1) and sum K} or {size (n-1) and (sum K-arr[n-1])}

So if you draw the recursion tree there will be many such sub-problem which will be overlapping ones. That means we will re-compute same sub-problems again and again. That’s why we need to store the value of sub-problems and use dynamic programming.

Converting to dynamic programming:

    1)  Initialize  dp[n+1][sum+1] which is a Boolean table to false
    2)  Convert the base cases for recursion
        for i=1 to sum
            dp[0][i]=false;
        for i=0 to n
            dp[i][0]=true;
    3)  Build the table as per the recursion formula.
        for i=1 to sum
            for j=1 to n
                //if sub-sum i>jth element then only we can take that
                if(i>=arr[j-1])   
                    //consider both case mentioned in solution approach
                    dp[j][i]=dp[j-1][i] | dp[j-1][i-arr[j-1]];   
                else                       // don't take jth element
                    dp[j][i]=dp[j-1][i];

                if(i==sum)
                    if(dp[j][i]){
                        return true;
                End If
            end for
        end for

    4)  If not returned from the loop  
            return false;

C++ Implementation

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

bool subsetSum(vector<int> arr, int n, int sum)
{
    //DP matrix
    bool dp[n + 1][sum + 1];

    memset(dp, false, sizeof(dp));

    //base case
    for (int i = 1; i <= sum; i++)
        dp[0][i] = false;
	
    for (int i = 0; i <= n; i++)
        dp[i][0] = true;
	
    //build the table
    for (int i = 1; i <= sum; i++) {
        for (int j = 1; j <= n; j++) {
            if (i >= arr[j - 1])
                dp[j][i] = dp[j - 1][i] | dp[j - 1][i - arr[j - 1]];
            else
                dp[j][i] = dp[j - 1][i];

            if (i == sum) {
                if (dp[j][i]) {

                    return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    int t, n, k, item;
	
    cout << "Enter array length,n\n";
    cin >> n;
	
    cout << "Enter sum,K\n";
    cin >> k;
	
    cout << "Enter elements\n";
    vector<int> a;
    for (int j = 0; j < n; j++) {
        scanf("%d", &item);
        a.push_back(item);
    }

    if (subsetSum(a, n, k))
        cout << "yes\n";
    else
        cout << "no\n";

    return 0;
}

Output

RUN 1:
Enter array length,n
5
Enter sum,K
11
Enter elements
5 6 7 3 9
yes

RUN 2:
Enter array length,n
5
Enter sum,K
22
Enter elements
5 6 7 3 9
yes