Subset Sum: Backtracking vs DP — When to Pick Each

Problem Statement#

The subset-sum family asks variations of one core question: given integers nums and a target T, does some subset sum exactly to T? The variants are:

• Existence (LeetCode 416): can we partition nums into two subsets of equal sum? Equivalent to asking if a subset sums to total / 2.
• Count (LeetCode 494 — Target Sum): how many subsets sum to T?
• Min count (LeetCode 322 — Coin Change): fewest elements that sum to T (with reuse).
• Enumeration (LeetCode 39, 40 — Combination Sum I/II): list all subsets that sum to T.

The interview decision is always: enumerate vs decide. If you must list every subset, backtracking is the only option. If you only need a yes/no, a count, or an optimum, DP wins.

Why This Problem Matters#

Subset sum is the canonical bridge between recursion and DP in interviews. Amazon, Google, and Meta use the partition variants (LC 416, LC 494) to test whether candidates can recognize the 0/1 knapsack pattern and write the rolling-array DP without bugs. The combination-sum variants (LC 39, LC 40) test backtracking purity. Understanding both ends of this spectrum and knowing when to switch is what separates a junior signal from a senior signal.

There is also the ML-systems angle: subset sum is NP-complete in the strong sense (large numbers), but pseudo-polynomial in the small-target case via DP. Articulating that distinction earns serious interviewer respect.

The Core Insight (decision tree / state space)#

The recursive structure is identical for both backtracking and DP:

solve(idx, target) =
    solve(idx + 1, target)            // skip nums[idx]
    OR solve(idx + 1, target - nums[idx])  // take nums[idx]

The decision tree has 2^n leaves. Backtracking traverses the tree explicitly to enumerate paths that hit target == 0. DP collapses the tree by memoizing on (idx, target) because many paths share the same state. The DP table has n * (T + 1) cells, giving the famous O(n * T) pseudo-polynomial bound.

For combination-sum problems with reuse (LC 39), the DP table is identical but the recurrence allows solve(idx, target - nums[idx]) (stay at idx) instead of advancing. For unbounded knapsack with min count (LC 322), use a 1D forward pass.

Visual Dry Run (recursion tree)#

For nums = [1, 5, 11, 5], target 11:

                 solve(0, 11)
              /                \
        skip 1                  take 1
       solve(1, 11)          solve(1, 10)
        /     \                /      \
     skip 5   take 5         skip 5   take 5
    solve(2,11) solve(2,6)   solve(2,10) solve(2,5)
       ...        ...           ...        ...

DP collapses repeated (idx, target) nodes. Backtracking enumerates the actual subsets like [1, 5, 5] and [11] — both sum to 11.

Solution (Optimal) — Python + JavaScript with backtracking template, complexity#

LC 416 — DP for partition existence:

def canPartition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for t in range(target, x - 1, -1):
            dp[t] = dp[t] or dp[t - x]
    return dp[target]

function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const x of nums) {
    for (let t = target; t >= x; t--) {
      dp[t] = dp[t] || dp[t - x];
    }
  }
  return dp[target];
}

Backtracking for full enumeration (LC 39 style, no reuse):

def subset_sum_all(nums, target):
    nums.sort()
    result, current = [], []
 
    def backtrack(start, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break  # sorted, so larger items also exceed
            current.append(nums[i])
            backtrack(i + 1, remaining - nums[i])
            current.pop()
 
    backtrack(0, target)
    return result

Complexity: DP is O(n times T) time and O(T) space (1D rolling). Backtracking is O(2^n) time and O(n) recursion depth. Bitset DP in C++ pushes the constant down to O(n times T / 64).

Common Mistakes#

• Iterating the inner DP loop forward instead of backward for 0/1 knapsack. Forward iteration allows reusing the same element, breaking the constraint.
• Forgetting the if total % 2: return False early exit in LC 416 — saves time and avoids subtle bugs.
• Using backtracking for existence checks. It is asymptotically worse than DP and will TLE on adversarial inputs.
• For combination sum with duplicates (LC 40), forgetting to skip nums[i] == nums[i-1] at the same recursion level — produces duplicate combinations.

Interview Tips#

• Start by classifying the problem: existence, count, optimum, or enumeration. The classification determines DP vs backtracking.
• Mention the pseudo-polynomial bound out loud: "DP runs in O(n times T) which is polynomial in target value but exponential in target's bit-width."
• For 0/1 knapsack, immediately optimize to a 1D rolling array — interviewers expect it.
• For backtracking, emphasize sort-and-prune: sort ascending, break the loop when nums[i] > remaining.

Follow-up Questions#

• Target Sum (LC 494): assign + or - to each element to reach T. Reduces to subset sum after algebra.
• Last Stone Weight II (LC 1049): minimize |sum(A) - sum(B)| where A and B partition nums.
• Combination Sum I (LC 39): enumeration with reuse.
• Combination Sum II (LC 40): enumeration without reuse and with duplicates.
• Coin Change (LC 322): unbounded min-count knapsack.

Key Takeaways#

• Classify before coding: existence, count, optimum, or enumeration.
• DP wins for decide and count; backtracking wins for enumeration.
• 0/1 knapsack uses a backward inner loop; unbounded knapsack uses a forward inner loop.
• The DP recurrence dp[t] = dp[t] or dp[t - x] is the partition-equal-subset-sum heart.
• Bitset DP in C++ achieves O(n times T / 64) for huge targets — useful for competitive programming.
• A FAANG interview staple that tests pattern recognition between recursion and DP.

Sources:

• Partition Equal Subset Sum - LeetCode
• 416. Partition Equal Subset Sum - In-Depth Explanation