Combination Sum

You are given an array of distinct integers nums and a target integer. Your task is to return a list of all unique combinations of nums where the chosen numbers sum to target.

The same number may be chosen from nums an unlimited number of times. Two combinations are the same if the frequency of each of the chosen numbers is the same, otherwise they are different.

You may return the combinations in any order and the order of the numbers in each combination can be in any order.

Examples

• 1 ≤ nums.length ≤ 20
• 2 ≤ nums[i] ≤ 30
• All elements of nums are distinct.
• 2 ≤ target ≤ 40

Prerequisites

Before attempting this problem, you should be comfortable with:

• Recursion - Understanding how recursive function calls work and how to define base cases.
• Backtracking - The pattern of exploring choices, making a decision, recursing, and then undoing the decision.
• Arrays/Lists - Working with dynamic lists and understanding how to add/remove elements.

1. Standard Backtracking

Intuition

We want to build all combinations of numbers that add up to the target. Each number can be used multiple times, so at every index we have two choices:

• Include the current number - stay at the same index (because we can reuse it).
• Skip the current number - move to the next index.

We explore all possible choices using backtracking. Whenever the running total equals the target, we store that combination. If the total becomes greater than the target or we run out of numbers, we stop exploring that path.

Define a recursive function dfs(i, currentList, total):
  If total == target:
    Add a copy of currentList to the result
    Return
  
  If i >= len(nums) or total > target:
    Return (stop exploring)
    
  // Choice 1: Include nums[i]
  Add nums[i] to currentList
  dfs(i, currentList, total + nums[i])  // Stay at same index i
  Remove nums[i] (backtrack)
  
  // Choice 2: Skip nums[i]
  dfs(i + 1, currentList, total)

2. Backtracking (Optimal with Early Pruning)

Intuition

This optimized backtracking solution avoids exploring useless paths by using sorting + early stopping.

We sort the numbers so that once a number makes the sum exceed the target, all numbers after it will also exceed the target - we can safely stop exploring further (break / return). At each position, we try every number starting from index i, allowing reuse of the same number. We build combinations step-by-step, and whenever the running total equals the target, we record the current list.

Sort nums so we can stop early when the sum exceeds the target.

Define a recursive function dfs(i, currentList, total):
  If total == target:
    Add a copy of currentList to the result
    Return
    
  Loop j from i to len(nums) - 1:
    If total + nums[j] > target:
      Stop the loop (no need to check larger numbers)
      
    Add nums[j] to currentList
    dfs(j, currentList, total + nums[j])  // reuse allowed (j instead of j+1)
    Remove last element (backtrack)

Start recursion with dfs(0, [], 0) and return the result.

Time Complexity: O(2^(Target / MinElement)) since the maximum depth of the tree is bounded by the smallest element in the array.

Space Complexity: O(Target / MinElement) for the maximum recursion stack depth.

Common Pitfalls

Moving to Next Index After Including an Element

Since each number can be used unlimited times, after including nums[i], you should stay at index i, not move to i + 1. Moving forward prevents reusing the same element.

# Wrong: can't reuse the same number cur.append(nums[i]) dfs(i + 1, cur, total + nums[i]) # Correct: stay at same index to allow reuse cur.append(nums[i]) dfs(i, cur, total + nums[i])

Generating Duplicate Combinations

Without maintaining an index i, you might generate [2,3] and [3,2] as separate combinations. Always iterate from the current index forward, never backward, to ensure each combination is generated only once in a deterministic order.

Not Pruning When Sum Exceeds Target

Continuing recursion when total > target wastes time exploring invalid paths. With a sorted input, you can break early once total + nums[j] > target since all subsequent numbers in the array are guaranteed to be larger.

# Inefficient: explores all paths for j in range(i, len(nums)): dfs(j, cur, total + nums[j]) # Optimized: stop early when sum exceeds target for j in range(i, len(nums)): if total + nums[j] > target: return dfs(j, cur, total + nums[j])