Subset/Subsequence Sum Equal To K | Solution | 4 Different Methods

 

Subset/Subsequence Sum Equal To K

Problem Statement

You are given an array/list ‘ARR’ of ‘N’ positive integers and an integer ‘K’. Your task is to check if there exists a subset in ‘ARR’ with a sum equal to ‘K’.

Note: Return true if there exists a subset with sum equal to ‘K’. Otherwise, return false.

For Example :

If ‘ARR’ is {1,2,3,4} and ‘K’ = 4, then there exists 2 subsets with sum = 4. These are {1,3} and {4}. Hence, return true.

Input Format :

The first line contains a single integer T representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘K’ representing the size of the input ‘ARR’ and the required sum as discussed above.

The next line of each test case contains ‘N’ single space-separated integers that represent the elements of the ‘ARR’.

Output Format :

For each test case, return true or false as discussed above.
Output for each test case will be printed in a separate line.

Note:

You don’t need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10^3
0 <= ARR[i] <= 10^9
0 <= K <= 10^3

Time Limit: 1 sec

Sample Input 1:

2
4 5
4 3 2 1
5 4
2 5 1 6 7

Sample Output 1:

true
false

Explanation For Sample Input 1:

In example 1, ‘ARR’ is {4,3,2,1} and ‘K’ = 5. There exist 2 subsets with sum = 5. These are {4,1} and {3,2}. Hence, return true.
In example 2, ‘ARR’ is {2,5,1,6,7} and ‘K’ = 4. There are no subsets with sum = 4. Hence, return false.

Sample Input 2:

2
4 4
6 1 2 1
5 6
1 7 2 9 10

Sample Output 2:

true
false

Explanation For Sample Input 2:

In example 1, ‘ARR’ is {6,1,2,1} and ‘K’ = 4. There exist 1 subset with sum = 4. That is {1,2,1}. Hence, return true.
In example 2, ‘ARR’ is {1,7,2,9,10} and ‘K’ = 6. There are no subsets with sum = 6. Hence, return false.

Solution
We can generate all possible subsets and see if the sum of all the elements in that subset equals to k. If yes we can return true.

Using DP & Recursion
1. Express everything in terms of index and target
2. Explore what we can do with index and target
3. If we get the target return True

Let's see the Algo:
let the function be f
f(ind,target){
if(target==0)return true;
if(ind==0)return (a[0]==target);
bool notTake=f(ind-1,target);
bool take=false;
    if(target>=arr[ind])take=f(ind-1,target-arr[ind]);
return take | notTake;
}

Time Complexity: 2^n;
Space Complexity: O(n)

Optimizing the Code:
As we are calling the same function again and again we can use DP to store the result.
f(ind,target){
if(target==0)return true;
if(dp[ind][target]!=-1)return dp[ind][target];
if(ind==0)return (a[0]==target);
bool notTake=f(ind-1,target);
bool take=false;
    if(target>=arr[ind])take=f(ind-1,target-arr[ind]);
return dp[ind][target]= take | notTake;
}

Tabulation:

Base Case:
1. if target==0 return true;
2. if ind==0 && arr[ind]==target return true;
3. dp[0][arr[0]]=true;
Form nested loops ind -> 1 to n-2
                            target-> 1 to K
for ( i=1 - > n-1 )
for ( target 1 -> K)

Time Complexity: O( N x target)
Space Complexity : O( N x target)
bool helper(int idx,int sum,vector<int>&arr){
    if(sum==0)return true;
    if(idx==0)return arr[0]==sum;
    bool notTake=helper(idx-1,sum,arr);
    bool take=false;
    if(arr[idx]<=sum)take=helper(idx-1,sum-arr[idx],arr);
    return take|notTake;
}
bool subsetSumToK(int n, int k, vector<int> &arr) {
   return helper(n-1,k,arr);
}

bool helper(int idx,int sum,vector<int>&arr,vector<vector<int>>&dp){
    if(sum==0)return true;
    if(dp[idx][sum]!=-1)return dp[idx][sum];
    if(idx==0)return arr[0]==sum;
    bool notTake=helper(idx-1,sum,arr,dp);
    bool take=false;
    if(arr[idx]<=sum)take=helper(idx-1,sum-arr[idx],arr,dp);
    return dp[idx][sum]=take|notTake;
}
bool subsetSumToK(int n, int k, vector<int> &arr) {
    vector<vector<int>>dp(n,vector<int>(k+1,-1));
   return helper(n-1,k,arr,dp);
}

bool subsetSumToK(int n, int k, vector<int> &arr) {
    vector<vector<bool>>dp(n,vector<bool>(k+1,false));
     if(arr[0]<=k)dp[0][arr[0]]=true;
    dp[0][0]=true;
    for(int i=1; i<n; i++){
        for(int j=0; j<=k; j++){
            bool notTake=dp[i-1][j];
            bool take=false;
            if(arr[i]<=j)take=dp[i-1][j-arr[i]];
            dp[i][j]=take|notTake;
            if(j==0)dp[i][j]=true;
        }
    }
    return dp[n-1][k];
}

bool subsetSumToK(int n, int k, vector<int> &arr) {
    vector<bool>pre(k+1,0);
    vector<bool>curr(k+1,0);
    if(arr[0]<=k)
    pre[arr[0]]=true;
    pre[0]=curr[0]=true;
    
    for(int i=1; i<n; i++){
        for(int j=1; j<=k; j++){
            bool nottake=pre[j];
            bool take=false;
            if(arr[i]<=j)take=pre[j-arr[i]];
            curr[j]=take| nottake;
        }
        pre=curr;
    }
    return pre[k];
}
Thank You for reading.