Q:

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\"

0

Subset Sum

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"

Example with explanation:

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

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

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 nth element the cases are:

  1. Consider the nth element as part of solution subset and recur for n-1 elements for obtaining sum (K-arr[n]).
  2. Don't consider nth 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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now