How Do You Solve the Subset Sum Problem?
Learn the subset sum dynamic programming solution, its recurrence, complexity, and how to answer this common interview question.
Expected Interview Answer
Subset sum asks whether some subset of a given set of numbers adds up exactly to a target value, solved with a 2D (or space-optimized 1D) dynamic programming table of booleans in O(n*target) time, where each item is either included or excluded when building up reachable sums.
Define dp[i][s] as true if some subset of the first i numbers sums exactly to s. For each number, dp[i][s] is true if dp[i-1][s] is already true (skip this number) or if s is at least the current number and dp[i-1][s - num] is true (include this number). The base case dp[0][0] is true since an empty subset sums to zero, and dp[0][s] for s > 0 is false. Because each number is used at most once, the inner loop over sums must iterate from high to low when the table is flattened to one dimension, so an already-updated sum in the current row is not reused within the same item's pass.
- Answers reachability without generating all 2^n subsets
- Pseudo-polynomial O(n*target) time, exact for bounded targets
- Foundation for partition, knapsack, and coin-change variants
- Space-optimizable to a single 1D boolean array
AI Mentor Explanation
A team manager wants to know if some combination of available bowlers' allotted overs can add up to exactly the overs remaining in an innings. For each bowler considered, the manager either leaves them out entirely or uses their full over allotment, tracking every exact over-total reachable so far. A total is reachable if it was already reachable without this bowler, or if subtracting this bowler's overs from the target lands on a total that was reachable before considering them. Working through bowlers one at a time and updating which totals are achievable is exactly how subset sum determines reachability without trying every possible combination of bowlers.
Step-by-Step Explanation
Step 1
Define the boolean state
dp[s] tracks whether sum s is achievable using items processed so far; dp[0] starts true.
Step 2
Iterate items outer, sums inner
For each number, consider including or excluding it for every possible sum up to the target.
Step 3
Traverse sums high to low
When flattened to 1D, loop sums from target down to the number's value so each item is used at most once.
Step 4
Check the target
dp[target] being true after processing all numbers means a valid subset exists.
What Interviewer Expects
- Correctly define dp[i][s] and the include/exclude recurrence
- State O(n * target) time and explain why it is pseudo-polynomial, not truly polynomial
- Explain why the 1D optimization must iterate sums in decreasing order
- Connect subset sum to the 0/1 knapsack problem as a special case
Common Mistakes
- Iterating sums low to high in the 1D version, causing an item to be reused multiple times
- Forgetting dp[0] = true as the base case (empty subset sums to zero)
- Confusing subset sum (0/1, each item once) with coin change (unbounded, items reusable)
- Not recognizing the algorithm is pseudo-polynomial and can be slow for very large target values
Best Answer (HR Friendly)
“Subset sum asks if some combination of numbers can add up to exactly a target, and I solve it by tracking every sum that's achievable so far as I consider each number one at a time, either skipping it or adding it in. It's the same core idea behind the knapsack problem, just answering yes-or-no instead of maximizing value.”
Code Example
def subset_sum(nums, target):
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for s in range(target, num - 1, -1):
if dp[s - num]:
dp[s] = True
return dp[target]
# Example
print(subset_sum([3, 34, 4, 12, 5, 2], 9)) # True (4 + 5)Follow-up Questions
- How would you reconstruct which numbers make up the achieving subset?
- How does subset sum relate to the 0/1 knapsack problem?
- How would this change if numbers could be reused (unbounded subset sum)?
- How would you handle negative numbers in the input?
MCQ Practice
1. In the 1D subset sum DP, why must the sum loop iterate from high to low?
Iterating high to low ensures dp[s - num] still reflects the state before this item was considered, so each item is used at most once.
2. What is the time complexity of the standard subset sum DP for n numbers and target sum T?
The DP fills a table of size roughly n by T, giving O(n * T) time — pseudo-polynomial since it depends on the numeric value of T.
3. What is the base case for subset sum DP?
A sum of 0 is always achievable using the empty subset, so dp[0] is initialized to true.
Flash Cards
What does dp[s] represent in subset sum? — Whether some subset of numbers processed so far sums exactly to s.
Why iterate sums high to low in the 1D version? — To avoid reusing the same item more than once within one pass.
What is the time complexity of subset sum DP? — O(n * target), which is pseudo-polynomial, not truly polynomial in input size.
How does subset sum relate to 0/1 knapsack? — It is a special case of 0/1 knapsack where value equals weight and you ask if a target weight is exactly reachable.