Last Updated: 18 May, 2021
Subset Sum Equal To K
Moderate
Asked in companies
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
Approaches
The idea is to generate all possible subsets and check if any of them sums up to ‘K’. This can be done through recursion.
Here is the algorithm:
subsetSumToK(N , K , ARR):
- Initialize integer variable ‘ANS’ = ‘helper(ARR, N, K)’. Here ‘helper’ is the recursive function that returns true/false.
- If ‘ANS’ is equal to 1 then:
- Return true.
- Else:
- Return false.
helper(ARR, N, K):
- Base case: If ‘N’ is less than or equal to 0:
- If ‘K’ is equal to 0:
- Return 1.
- Else:
- Return 0.
- If ‘K’ is equal to 0:
- Initialize integer variable ‘X’ = ‘helper(ARR, N-1, K)’. Here, ‘ARR[N-1]’ is not included in the sum.
- Initialize integer variable ‘Y’ = ‘helper(ARR, N-1, K - ARR[N-1])’. Here, ‘ARR[N-1]’ is included in the sum.
- Return ‘X’ OR ‘Y’.
The idea is to use dynamic programming to generate all the possible subsets and check if these subsets sum up to ‘K’.
Here is the algorithm:
- Create a boolean 2D array/list ‘DP’ of size (‘N+1’)*(‘K+1’) i.e. ‘DP[N+1][K+1]’.
- If ‘K’ is equal to 0, then the answer should be ‘true’. Hence, run a loop from 0 to ‘N’ (say iterator = ‘i’):
- ‘DP[i][0]’ = true.
- If ‘K’ is not zero but ‘ARR’ is empty then the answer should be ‘false’. Hence, run a loop from 1 to ‘K’ (say iterator = ‘i’):
- ‘DP[0][i]’ = false.
- To fill the ‘DP’ table, run a loop from 1 to ‘N’ (say iterator = ‘i’):
- Run a loop from 1 to ‘K’ (say iterator = ‘j’):
- ‘DP[i][j]’ = ‘DP[i-1][j]’.
- If ‘j’ is greater than equal to ‘ARR[i-1]’:
- ‘DP[i][j]’ = ‘DP[i][j]’ OR ‘DP[i-1][j - ARR[i-1]]’.
- Run a loop from 1 to ‘K’ (say iterator = ‘j’):
- Finally, return ‘DP[N][K]’.
The idea is to generate all possible subsets and check if any of them sums up to ‘K’. Along with that, we will use memoization to store previously calculated results to avoid repetition and hence improving the time complexity.
Here is the algorithm:
subsetSumToK(N , K , ARR):
- Create 2D array/list ‘MEMO’ of size (‘N’+1) * (‘K’ + 1) i.e. ‘MEMO[N+1][K+1]’.
- Store -1 at all indices of ‘MEMO’. (This ‘MEMO’ array/list will be used to store the previously calculated results).
- Initialize integer variable ‘ANS’ = ‘helper(ARR, N, K, MEMO)’. Here ‘helper’ is the recursive function that returns true/false.
- If ‘ANS’ is equal to 1 then:
- Return true.
- Else:
- Return false.
helper(ARR, N, K, MEMO):
- Base case: If ‘N’ is less than or equal to 0:
- If ‘K’ is equal to 0:
- Return 1.
- Else:
- Return 0.
- If ‘K’ is equal to 0:
- If ‘MEMO[N][K]’ is not equal to -1, i.e. value for this combination of ‘N’ and ‘K’ is already calculated, then:
- Return ‘MEMO[N][K]’.
- Initialize integer variable ‘X’ = ‘helper(ARR, N-1, K, MEMO)’. Here, ‘ARR[N-1]’ is not included in the sum.
- Initialize integer variable ‘Y’ = ‘helper(ARR, N-1, K - ARR[N-1], MEMO)’. Here, ‘ARR[N-1]’ is included in the sum.
- ‘MEMO[N][K]’ = ‘X’ OR ‘Y’.
- Return ‘MEMO[N][K]’.