Subset Sum Problem
nums holds positive integers, and target is a positive integer. Can you choose some of the values, each position at most once, so that they sum to exactly target? Return true when you can and false when no choice works.
Function
- numsinteger-array
- the positive values you may pick from
- targetinteger
- the exact sum the picked values must reach
- Returnsboolean
- true when some of the values add up to exactly target, false otherwise
Constraints
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 1041 ≤ target ≤ 104
Examples
- Input
- nums = [8, 3, 11, 5, 7]target = 15
- Output
- true
- Explanation
- 8 + 7 = 15, so the answer is
true. The pick 3 + 5 + 7 works too; one pick is enough.
- Input
- nums = [6, 9, 12, 15]target = 20
- Output
- false
- Explanation
- Every value is a multiple of 3, so every sum of them is a multiple of 3 as well. 20 is not, so the answer is
false.
- Input
- nums = [4, 1, 2]target = 8
- Output
- false
- Explanation
- All three values together make 4 + 1 + 2 = 7, which is less than 8, so no pick can reach it and the answer is
false.
Follow-up
Two equal values at different positions count as different picks. How many picks reach target?
Hints
Open them one at a time. Each one gives away a little more.
Start with
nums[0]. If your pick includes it, the other values must maketarget-nums[0]. If not, they must maketarget. Both are the same question on a shorter array.Whether the values from position
ion can make a sumrdepends oniandronly, andrnever goes abovetarget. So there are at most about 200 × 10^4 different questions, and each one can be answered once.Use one boolean per sum from 0 to
target, with only sum 0 reachable at first. Add the values one by one: a sumsbecomes reachable whens-numalready was. Update the sums from high to low so a value is not used twice, and read the answer attarget.
Solution
A pick is a yes or no for each value, so 200 values give 2^200 picks. Only sums up to target ≤ 10^4 matter, though. Record which sums the values so far can make: each new value shifts that record by its size, and the search becomes a table of n × target booleans.
Take or skip each value
Correct, but does not finish on the largest tests
Intuition
canMake(i, remaining) asks whether the values from position i on can make exactly remaining. Take nums[i] when it fits, which leaves remaining-nums[i] for the rest; if that fails, skip it. Every pick is one path, so the search finds a pick whenever one exists.
When none exists, it walks them all. With 200 multiples of 3, each at most 300, and a target of 9998, no pick works, yet any 33 values stay under the target: over 10^37 paths.
Algorithm
- Write
canMake(i, remaining). - A
remainingof 0 means the pick is complete: return true. With no values left and something still to make, return false. - If
nums[i] ≤ remainingandcanMake(i+1, remaining-nums[i])is true, return true. - Otherwise return
canMake(i+1, remaining). - Return
canMake(0, target).
def isSubsetSum(nums, target):
n = len(nums)
# Can some of nums[i], nums[i+1], ... add up to exactly remaining?
def can_make(i, remaining):
if remaining == 0:
return True
if i == n:
return False
if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
return True # take nums[i]
return can_make(i + 1, remaining) # skip it
return can_make(0, target)Fill a table of reachable sums
Intuition
The recursion depends only on a position and a remaining sum between 0 and target, and many paths reach the same pair. Fill a table instead. made[i][s] is true when a pick from the first i values sums to exactly s; the empty pick makes 0. With num = nums[i-1], sum s is made if it was made without num, made[i-1][s], or if num completes s-num, made[i-1][s-num] with s ≥ num.
In the first example, after the 8 the made sums are 0 and 8. The 3 adds 3 and 11, the 11 adds only 14, the 5 adds 5 and 13, and 8 + 7 reaches 15. At the limits the table has 201 × 10001 cells, about 2 × 10^6 steps.
Algorithm
- Allocate
madeas n+1 rows by target+1 booleans, all false. Markmade[0][0]true for the empty pick. - Row
ihandles the valuenum = nums[i-1], fori= 1 to n. - For each sum
sfrom 0 totarget, setmade[i][s]tomade[i-1][s]. - If
s ≥ numandmade[i-1][s-num]is true, setmade[i][s]to true. - Return
made[n][target].
def isSubsetSum(nums, target):
n = len(nums)
# made[i][s]: some of the first i values add up to exactly s
made = [[False] * (target + 1) for _ in range(n + 1)]
made[0][0] = True
for i in range(1, n + 1):
num = nums[i - 1]
for s in range(target + 1):
# leave num out, or put it in on top of a sum of s-num
made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
return made[n][target]One row of sums, updated from the top
Intuition
Each row reads only the row before it, so one array made[s] can hold it. Overwrite it upward and a value feeds itself: with nums = [5] and target 10, s = 5 turns true, then s = 10 reads that fresh entry, using the 5 twice.
Go from target down to num instead. The read at s-num hits a lower cell the walk has not rewritten, so it sees the row from before num. A made sum stays made, so you can stop as soon as made[target] is true. Memory drops to target + 1 booleans.
Algorithm
- Start with a single array of
target + 1booleans in which onlymade[0]is true. - Take the values in order. For each
num, runsdownward fromtargettonum. - Wherever
made[s-num]holds, markmade[s]. - Stop with
trueas soon asmade[target]is marked. - If every value is used up first, the answer is
false.
def isSubsetSum(nums, target):
# made[s]: some of the values seen so far add up to exactly s
made = [False] * (target + 1)
made[0] = True
for num in nums:
# Downward, so made[s - num] still ignores num
for s in range(target, num - 1, -1):
if made[s - num]:
made[s] = True
if made[target]:
return True
return False
Pitfalls and edge cases
- An upward loop over the sums uses a value twice:
[3]with target 9 answers true. - Forgetting
made[0] = true. Every sum builds on the empty pick, so every answer comes out false. - Picking the largest values first. On
[6, 5, 5]with target 10, taking 6 leaves 4, which nothing makes, while 5 + 5 = 10. - A value above
target, as in[10000]with target 1, must change nothing. Swift'snum...targetstops the program and R's(num+1):(target+1)counts backward, so checknum ≤ targetfirst. - In Lua and R the entry for sum
slives at indexs + 1.
Frequently asked questions4
What is the time complexity of the subset sum problem?
The table costs O(n × target) time, about 2 × 10^6 steps for 200 values and a target of 10^4, and one row cuts memory to O(target). The cost follows the numeric size of the target, so the method is pseudo-polynomial and useless for a target like 10^18. In general, subset sum is NP-complete.
How is Subset Sum related to Partition Equal Subset Sum and the 0/1 knapsack?
Partition Equal Subset Sum is Subset Sum with target = total / 2, after checking that the total is even. Subset Sum is a 0/1 knapsack where each value is its own weight and the bag must be filled exactly, so the table holds booleans instead of best values.
Does subset sum work with negative numbers?
The idea works, the code above does not. With negatives the reachable sums run from the total of the negatives to the total of the positives, so shift every index by that lowest sum and fill the row the same way. A value larger than the remaining sum can no longer be skipped.
How do you find which values make the target?
Keep the full table and start at made[n][target]. Step up one row at a time: if made[i-1][s] is true, nums[i-1] was not needed; otherwise record it and subtract it from s. You stop at sum 0 with one valid pick.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def isSubsetSum(nums, target):
# Write code hereTest #1
Test #2
Test #3
Arguments
nums = [8, 3, 11, 5, 7] target = 15
Expected Output
true