What Is the Subset Sum Problem? From O(2^n) to O(n·T)
- Subset sum problem asks whether any subset of an array sums to exactly T; each element used at most once.
- Brute force enumerates all 2^n subsets and is NP-complete in the general case (Karp 1972), but a bounded target T allows pseudo-polynomial O(n·T) DP.
- The 2D DP recurrence is dp[i][s] = dp[i-1][s] OR dp[i-1][s-num], building reachable sums element by element from a base case of dp[0] = True.
- Backward iteration is the critical space-optimization detail: scanning s from high to low ensures each element contributes at most once, not like unbounded knapsack (coin change).
- LeetCode 416 (partition equal subset sum) and LeetCode 494 (target sum) are the two most common interview disguises of this pattern.
- The recognition signal: keywords like "partition," "split into equal groups," or "reach exactly a value using elements once" all reduce to a subset sum query on a derived target.
- Three common bugs: forward scan (enables reuse), missing dp[0] = True base case, and negative values that require index shifting.
You have a pile of numbers. You have a target. The question sounds innocent: can any combination of those numbers add up to exactly that target?
It sounds like something you could solve in your head. For seven numbers, sure. For forty? You would die of old age before your laptop finished. That's the subset sum problem, and the DP insight that tames it shows up, in thin disguise, in about a third of the dynamic programming problems you'll face in a coding interview.
What Exactly Is the Subset Sum Problem?
Given an array of non-negative integers nums and a target integer T, determine whether any subset of nums sums to exactly T. Each element may be used at most once.
nums = [3, 1, 5, 2] T = 6 # {1, 5} → 1 + 5 = 6 ✓ # {1, 3, 2} → 1 + 3 + 2 = 6 ✓ # Answer: True
Subsets, not subarrays. Order does not matter. Elements cannot repeat. The question is just whether the target is reachable.
Brute Force: Technically Correct, Practically Insane
The honest solution: generate every subset, check its sum.
An array of n elements has 2^n subsets. Each element is independently either in or out.
def subset_sum_brute(nums: list[int], target: int) -> bool: n = len(nums) for mask in range(1 << n): current_sum = 0 for i in range(n): if mask & (1 << i): current_sum += nums[i] if current_sum == target: return True return False
For n = 20, this checks over a million subsets. For n = 40, a trillion. For n = 64, more subsets than there are atoms in your body, roughly. The brute force is not a bug in your reasoning. It reflects something real: subset sum is NP-complete, and Richard Karp proved it in 1972 alongside 20 other problems that also refuse to go quietly.
But here is where it gets interesting. That hardness proof assumes unbounded integers. When your target T is bounded, dynamic programming drops the complexity to O(n × T). That is pseudo-polynomial time, not polynomial in the strict theoretical sense, but it handles T up to hundreds of thousands without breaking a sweat.
The DP Insight: You're Answering the Same Question Over and Over
Look at the brute force recursion tree. Suppose you include nums[0] and skip nums[1]. At some point you will ask: "can the remaining elements form the remaining sum?" You will ask that same question from a completely different branch. Then again. Then again.
That is the overlapping subproblems pattern. Cache the answers and you stop repeating work.
Define the subproblem: can I form exactly sum s using only the first i elements?
Let dp[i][s] be True if some subset of nums[0..i-1] sums to s, False otherwise.
Two Choices Per Element, One Cell Per Answer
For element nums[i-1] and target sum s, two choices:
- Skip it. Was
sreachable before this element:dp[i-1][s]. - Include it (only valid when
nums[i-1] <= s). Wass - nums[i-1]reachable before:dp[i-1][s - nums[i-1]].
If either option is True, then dp[i][s] = True.
dp[i][s] = dp[i-1][s] OR dp[i-1][s - nums[i-1]] (when nums[i-1] <= s)
dp[i][s] = dp[i-1][s] (otherwise)
Base case: dp[i][0] = True for all i. The empty subset sums to zero. Always.
Build It By Hand
nums = [1, 3, 2], T = 4:
| s=0 | s=1 | s=2 | s=3 | s=4 | |
|---|---|---|---|---|---|
| i=0 (no elements) | T | F | F | F | F |
| i=1 (consider 1) | T | T | F | F | F |
| i=2 (consider 3) | T | T | F | T | T |
| i=3 (consider 2) | T | T | T | T | T |
Row i=2, column s=4: dp[1][4] is F (skip 3), dp[1][4-3] = dp[1][1] is T (include 3). So dp[2][4] = True.
Row i=3, column s=2: dp[2][2] is F (skip 2), dp[2][2-2] = dp[2][0] is T (include 2). So dp[3][2] = True.
The bottom-right cell dp[3][4] is True. The answer is yes: 1 + 3 = 4.
def subset_sum_2d(nums: list[int], target: int) -> bool: n = len(nums) dp = [[False] * (target + 1) for _ in range(n + 1)] for i in range(n + 1): dp[i][0] = True for i in range(1, n + 1): for s in range(1, target + 1): dp[i][s] = dp[i - 1][s] if nums[i - 1] <= s: dp[i][s] = dp[i][s] or dp[i - 1][s - nums[i - 1]] return dp[n][target]
Time: O(n × T). Space: O(n × T).
Halve the Space: One Row Is Enough
Row i only ever reads from row i-1. You do not need the full table. Keep one array and update it in place.
def subset_sum(nums: list[int], target: int) -> bool: dp = [False] * (target + 1) dp[0] = True for num in nums: for s in range(target, num - 1, -1): dp[s] = dp[s] or dp[s - num] return dp[target]
O(T) space. Same O(n × T) time.
Why Backward? (Read This Twice)
This is the most important detail in the whole approach, and also the most popular way to throw away an easy interview question. If you scan forward (low to high), when you compute dp[s], the value dp[s - num] might already reflect that num was added earlier this same pass. Which means num can contribute more than once. Which means you just accidentally solved coin change, a completely different problem.
Backward scan ensures that when you read dp[s - num], it still reflects the state before this element was considered. One element, one use.
The sneaky part: scanning forward produces wrong answers only on specific inputs, not all of them. Your solution looks right until it doesn't. This is the same principle that separates 0/1 knapsack from unbounded knapsack, covered in depth in 0/1 Knapsack: The DP Pattern Explained.
Subset Sum in a Trench Coat
Subset sum almost never shows up with that name on a problem sheet. It shows up disguised as a more complicated-sounding question, hoping you won't recognize the skeleton underneath.
Partition Equal Subset Sum (LeetCode 416) is the most common form. Can you split an array into two subsets with equal sums? Compute the total. If it's odd, return False immediately. Otherwise: can any subset sum to total // 2? Direct reduction.
def can_partition(nums: list[int]) -> bool: total = sum(nums) if total % 2 != 0: return False target = total // 2 dp = [False] * (target + 1) dp[0] = True for num in nums: for s in range(target, num - 1, -1): dp[s] = dp[s] or dp[s - num] return dp[target]
Target Sum (LeetCode 494) assigns a + or - to each element to reach a target. This is the count variant. The DP structure is nearly identical; you track counts instead of booleans.
Last Stone Weight II (LeetCode 1049) asks for the minimum weight remaining after repeatedly smashing stones. It reduces to: find the largest subset whose sum does not exceed total // 2. Another subset sum query, different costume.
The recognition signal: whenever you see "partition," "assign signs," "split into two groups that balance," or "reach exactly a value using a subset," ask whether it collapses to subset sum of some target derived from the total. The complement is coin change: if elements are reusable, that's coin change; if each element is used at most once, that's subset sum.
Three Bugs That Will Cost You Points
Scanning forward instead of backward. This single error transforms your solution into one that solves a different problem, producing wrong answers only on specific inputs. It is genuinely hard to catch without a well-chosen test case, which is exactly why interviewers use it as a quiet filter.
Setting the wrong base case. dp[0] must be True. The empty subset sums to zero. Skip this and your function returns False for every input while looking completely reasonable to anyone reading it.
Assuming non-negative inputs. Negative values break index-based DP because s - num can go negative. If the problem includes negatives, shift all values up by the absolute minimum and adjust the target. The structure stays the same; the index range shifts. Memoization with a hash map (top-down DP) handles negatives more cleanly than tabulation if you need to sidestep the index problem entirely.
Practice This Out Loud
Subset sum looks easy until you confuse it with coin change, forget the backward scan, or miss the disguised reduction in a partition problem. The gap between knowing the theory and executing under pressure is a communication gap as much as a knowledge gap. If you want to practice talking through DP reductions out loud, SpaceComplexity runs voice-based mock interviews with rubric feedback on exactly these problem types.
Complexity Summary
| Approach | Time | Space |
|---|---|---|
| Brute force (all subsets) | O(2^n) | O(n) recursion stack |
| 2D DP table | O(n × T) | O(n × T) |
| 1D DP (optimized) | O(n × T) | O(T) |