Intermediate Level
Implement the subsetSumExists method that checks whether any subset can produce the target sum.
The input contains an integer array nums, its length size, and a target value target. Your task is to check whether any subset of the array has a sum equal to the target.
Each element can be used at most once. For example, in [3,34,4,12,5,2] with target 9, the subset [4,5] makes 9, so the answer is true.
Example 1
Input
nums (int[]) =
[3,34,4,12,5,2]size (int) =
6target (int) =
9Returns (boolean)
trueExample 2
Input
nums (int[]) =
[1,2,3]size (int) =
3target (int) =
7Returns (boolean)
falseExample 3
Input
nums (int[]) =
[2,4,6]size (int) =
3target (int) =
6Returns (boolean)
trueUse dynamic programming to track which sums are possible.
Create a boolean array where dp[x] means a subset with sum x can be formed. Start with dp[0] = true, because sum zero is possible by choosing no elements.
For each number, update the possible sums in reverse order. Reverse order is important because one number should not be reused multiple times in the same step.
Pseudocode:
function subsetSumExists(nums, size, target):
dp = boolean array of target + 1 values filled with false
dp[0] = true
for each num in nums:
for sumValue from target down to num:
if dp[sumValue - num] == true:
dp[sumValue] = true
return dp[target]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run