Subset/Subsequence Sum Equal To K

Problem Statement

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.``````
`SolutionWe 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 & Recursion1. Express everything in terms of index and target2. Explore what we can do with index and target3. If we get the target return TrueLet's see the Algo:let the function be ff(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 Kfor ( 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.`