Introduction
The Subset Sum problem asks: given a set (or multiset) of non-negative integers and a target value, does there exist a subset of the given numbers that sums exactly to the target? This is a foundational NP-complete problem in its general form, but when the target sum is bounded by a reasonably small value, it can be solved efficiently with pseudo-polynomial dynamic programming in O(n * sum) time. Subset Sum is closely related to the 0/1 Knapsack problem (it is essentially Knapsack where value equals weight and we only care about feasibility, not value maximization), and it underlies problems like partitioning an array into two equal-sum subsets.
Cricket analogy: Asking whether some combination of partnership scores can sum exactly to a declared target total is subset sum; it's hard in general but solvable efficiently with DP when the target is a reasonably bounded number of runs, and it's the feasibility twin of knapsack, ignoring value and just checking reachability.
Approach/Syntax
def subset_sum(nums, target):
n = len(nums)
# dp[i][s] = True if some subset of nums[:i] sums to exactly s
dp = [[False] * (target + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = True # empty subset always sums to 0
for i in range(1, n + 1):
for s in range(1, target + 1):
dp[i][s] = dp[i - 1][s] # exclude nums[i-1]
if nums[i - 1] <= s:
dp[i][s] = dp[i][s] or dp[i - 1][s - nums[i - 1]] # include nums[i-1]
return dp[n][target]Explanation
dp[i][s] is True if some subset of the first i elements of nums sums to exactly s. For each element nums[i-1], we have two choices: exclude it, in which case dp[i][s] inherits dp[i-1][s] (whether a subset of the first i-1 elements already achieves sum s); or include it (only valid if nums[i-1] <= s), in which case we need dp[i-1][s - nums[i-1]] to be True, meaning the remaining elements can make up the rest of the target. dp[i][s] is True if either choice works. The base case dp[i][0] = True for all i because the empty subset always sums to zero, regardless of which elements are available. The final answer is dp[n][target], indicating whether the full set can produce the target sum. This recurrence is structurally identical to 0/1 Knapsack, except we track boolean reachability of a sum instead of maximizing value subject to a weight constraint.
Cricket analogy: dp[i][s] is true if some combination of the first i partnership scores sums to exactly s; exclude the i-th score and inherit dp[i-1][s], or include it if it fits and check dp[i-1][s - score]; dp[i][0] is always true since zero total needs no partnerships at all.
Example
def subset_sum(nums, target):
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]
if __name__ == "__main__":
nums = [3, 34, 4, 12, 5, 2]
target = 9
# Trace: subset {4, 5} sums to 9, and {3, 4, 2} also sums to 9
print(subset_sum(nums, target)) # True
target2 = 30
print(subset_sum(nums, target2)) # False, no subset sums exactly to 30Complexity
The DP table has (n+1) rows and (target+1) columns, and each cell is computed in O(1) time, giving overall time and space complexity of O(n * target). This is called pseudo-polynomial because the complexity depends on the numeric value of the target, not just the number of input elements n — for very large targets this approach becomes impractical even though it is technically polynomial in n and target. Space can be reduced to O(target) by iterating the sum dimension from high to low within a single 1D array, reusing dp[s] and dp[s - nums[i-1]] from the previous iteration (the same rolling-array trick used in 0/1 Knapsack).
Cricket analogy: A table of (n+1) partnerships by (target+1) run totals, each cell O(1), gives O(n*target) time and space — pseudo-polynomial since it depends on the numeric run target, reducible to O(target) space by iterating totals high to low, the same rolling-array trick as knapsack.
Key Takeaways
- dp[i][s] = True if some subset of the first i numbers sums exactly to s; base case dp[i][0] = True for all i.
- Recurrence: dp[i][s] = dp[i-1][s] (exclude) OR dp[i-1][s - nums[i-1]] (include, only if nums[i-1] <= s).
- Time and space complexity are O(n * target), which is pseudo-polynomial since it depends on the numeric target value.
- Space can be reduced to O(target) using a 1D array updated from high sums to low sums.
- Subset Sum is structurally the boolean-feasibility variant of the 0/1 Knapsack problem.
Practice what you learned
1. What does dp[i][s] represent in the Subset Sum DP table?
2. Why is dp[i][0] = True for every i, including i = 0?
3. What is the time complexity of the standard Subset Sum DP algorithm, and why is it called 'pseudo-polynomial'?
4. How does the Subset Sum recurrence differ conceptually from the 0/1 Knapsack recurrence?
Was this page helpful?
You May Also Like
0/1 Knapsack Problem
Learn the classic 0/1 knapsack DP formulation, its O(nW) recurrence, and how to reconstruct the chosen items.
Coin Change Problem
Solve the minimum-coins and count-ways variants of the coin change problem using DP in O(n * amount) time.
Introduction to Dynamic Programming
Learn what dynamic programming is and the two conditions — overlapping subproblems and optimal substructure — that make it applicable.