# Subset Sum Equal To K | Coding Ninja Solution | CodeStudio

## Subset Sum Equal To K | CodingNinja Solution | CodeStudio

#### 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^9

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.``````
``bool subsetSumToK(int n, int k, vector<int> &arr){  vector<vector<bool>> dp(n, vector<bool>(k + 1, 0));  for (int i = 0; i < n; i++)    dp[i] = true;  dp[arr] = true;  for (int i = 1; i < n; i++)  {    for (int j = 1; 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;    }  }  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);  pre[arr] = true;  pre = curr = 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];}``