Subset Sum Equals Target
Subset Sum Equals Target: given an array of non-negative integers and a target, decide whether some subset sums to exactly the target.
- 1 <= n <= 100
- 1 <= target <= 10⁴
- 0 <= nums[i] <= 10⁴
- Non-negative values only — negatives break the DP table indexing
Intuition
Subset sum equals target asks whether any subset of an array adds up exactly to a given target. It is the foundational 0/1 knapsack problem — every element is taken once or not at all, and understanding it makes Partition Equal Subset Sum and Target Sum immediate.
The recursive framing is a single binary choice per element:
- For each element, either include it and reduce the target by its value, or exclude it and leave the target unchanged.
Exploring both branches for every element gives 2ⁿ paths, which is far too slow — but the same (index, remaining target) pair recurs across many different paths. That overlap is what memoisation and tabulation exploit.
The tabulated form defines dp[i][t] as whether target t is reachable using the first i elements. Base cases decide everything downstream: target 0 is always reachable by choosing nothing, and any positive target with no elements is unreachable.
Collapsing to one dimension requires iterating the target downward. Going upward reads cells this element has already updated in the same pass, which lets one element be used repeatedly and silently converts the problem to unbounded knapsack.
That downward sweep is the same rule that governs Ones and Zeroes and Partition Equal Subset Sum — the direction of iteration is what encodes at-most-once.
0/1 knapsack compressed to one dimension. The row index disappears because each item is processed once, but that only stays correct if the capacity loop runs downward — descending order guarantees dp[s - num] still refers to the previous item's row. Loop direction encoding "use once" versus "use unlimited" is the single most transferable fact in knapsack DP.
Approach
Before reading on: price up what counting everything costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n · target) time and O(target) space.
Frame it as a binary choice
Each element is either included, reducing the target by its value, or excluded, leaving the target unchanged. This take-or-skip structure is 0/1 knapsack in its simplest form.
Spot the overlapping subproblems
Plain recursion explores 2^n paths, but the same (index, remaining target) pair recurs across many of them. That repetition is exactly what a DP table removes.
Define the boolean state
dp[t] records whether target t is reachable. Set dp[0] = true — a sum of zero is always achievable by choosing nothing, and this base case seeds everything else.
Iterate the target downward
For each element, sweep the target from high to low. Sweeping upward reads cells this element already updated, allowing it to be reused and turning the problem into unbounded knapsack.
Apply the transition
Set dp[t] = dp[t] or dp[t - num] for every t >= num. A target is reachable if it already was, or if removing this element leaves a reachable one.
Return the target cell
After processing every element, dp[target] answers the question. No scan of the table is needed, since each cell already holds its final value.
Cost of the tabulation
Each element sweeps the target range once, giving O(n · target) time and O(target) space — pseudo-polynomial, since the cost scales with the target's value, not its digit count.
Solution & live demo
Common pitfalls
Iterating the sum upward
for s in range(num, target + 1):
if dp[s - num]: dp[s] = Truefor s in range(target, num - 1, -1):
if dp[s - num]: dp[s] = TrueAscending order lets a value updated by this item be read again by the same item, so one element gets reused any number of times — that's the unbounded variant. Descending guarantees dp[s - num] is still from the previous round.
Forgetting the empty-subset base case
dp = [False] * (target + 1)
dp = [False] * (target + 1) dp[0] = True
Sum 0 is always achievable by taking nothing, and that True is the seed every reachable sum chains back to. Without it the whole array stays false.
Stopping the inner loop at zero
for s in range(target, -1, -1):
for s in range(target, num - 1, -1):
Below num the expression s - num is negative, which in Python wraps to the end of the list and reads an unrelated entry. Stopping at num keeps every index valid.
Edge cases
Immediately True — the empty subset sums to 0, and dp[0] is seeded True.
The inner loop never runs, so dp stays all-False except dp[0] → False.
Harmless: a zero only re-marks sums already reachable, so the answer is unchanged.