Can some subset reach this sum?
For every number, either it's in the subset or it isn't — track every sum that's reachable either way. About 13 minutes.
Track totals, not selections
You have a few banknotes and want to know whether some of them add up to exactly 10. You don't need to know which notes, only whether 10 is possible.
So keep a checklist of every total from 0 to 10 and tick the ones you can make. At the start, only 0 is ticked: you can always make 0 by using nothing. Then bring in the notes one at a time.
Each new note extends every old total
When a new note arrives, every total you could already make can now be made bigger by that note. With a 3 in hand, 0 becomes 3. When a 7 arrives, 0 becomes 7 and 3 becomes 10.
One detail matters: walk the totals from the top down. Walking upward, the note you just added could be used again in the same pass, as if you had two copies of it.
can = [True] + [False] * target
for x in nums:
for s in range(target, x - 1, -1):
if can[s - x]:
can[s] = True
return can[target]Before any item, only 0 is reachable: the empty subset.
The notes are 2 and 5, and the target is 7. After both notes, is 7 ticked?
- AYes
- BNo
Show the answer
Yes. 2 + 5 = 7, so using both notes makes exactly 7.
Can some subset reach this sum?
Given an array nums of non-negative integers and a target, return true if some subset of nums (possibly all of it, possibly none) adds up to exactly target, or false otherwise.
nums = [3, 7, 5, 2], target = 10 → true
0 ≤ nums.length ≤ 200 · 0 ≤ nums[i] ≤ 1,000 · 0 ≤ target ≤ 10,000