Subset Sum Problem

Analogy categoryAnalogies

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

python

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

python

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 30

Complexity

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?

Edit Distance

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#SubsetSumProblem#Subset#Sum#Problem#Approach#StudyNotes#SkillVeris