Subset Sum
Intermediate
Return True if some subset of nums (possibly empty) adds up to exactly target.
For nums = [3, 34, 4, 12, 5, 2] and target = 9 the answer is True (4 + 5).
The starter code tries taking or skipping every number. It is correct but too slow when there is no answer.
Examples
Example 1
Input:
subset_sum([3, 34, 4, 12, 5, 2], 9)
Output:
True
Example 2
Input:
subset_sum([3, 34, 4, 12, 5, 2], 30)
Output:
False
Constraints
0 <= len(nums) <= 2001 <= nums[i] <= 10000 <= target <= 100000
Theory
Go to TheoryKeywords
dsa-sheetdynamic-programmingknapsack
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.