Combination Sum

The Combination Sum problem involves finding all unique combinations of numbers from a given set (`candidates`) that add up to a specific `target` number. Unlike finding subsets, numbers in `candidates` can be reused multiple times in a combination.

This problem is efficiently solved using a backtracking algorithm, which systematically builds combinations and prunes invalid paths early.

How it Works: Backtracking Depth-First Search

We employ a recursive depth-first search (DFS) approach. The core idea is to explore potential combinations by adding numbers one by one. If a path exceeds the target, we backtrack. If it matches the target, we record it.

def combinationSum(candidates, target):
    res = []

    def dfs(i, current_combination, current_sum):
        # Base case: target reached
        if current_sum == target:
            res.append(list(current_combination))
            return
        # Base case: invalid path (exceeded target or no more candidates)
        if i >= len(candidates) or current_sum > target:
            return

        # Decision 1: Include candidates[i]
        current_combination.append(candidates[i])
        dfs(i, current_combination, current_sum + candidates[i]) # Reuse candidates[i]
        current_combination.pop() # Backtrack

        # Decision 2: Exclude candidates[i] (move to next candidate)
        dfs(i + 1, current_combination, current_sum)

    dfs(0, [], 0)
    return res

Step-by-Step Execution

1. Start DFS: The process begins with an initial call to `dfs` at index 0, an empty `current_combination`, and a `current_sum` of 0. 2. Include Candidate: At each step, we first try to include the candidate at the current index (`candidates[i]`). We add it to `current_combination`, update `current_sum`, and recursively call `dfs` with the *same* index `i`. This allows for reusing the same number. 3. Check for Target/Exceed: Inside the recursive call, we check if `current_sum` equals `target`. If so, we've found a valid combination and add a copy of `current_combination` to our results. If `current_sum` exceeds `target` or we run out of candidates, the current path is invalid, and we return. 4. Backtrack: After exploring the path where `candidates[i]` was included, we `pop` it from `current_combination`. This is the backtracking step, resetting our state to explore alternative paths. 5. Exclude Candidate: Next, we make a recursive call to `dfs` with `i + 1`, effectively skipping `candidates[i]` and moving on to the next unique candidate. This ensures all combinations are explored. 6. Repeat: This process continues until all possible paths have been explored or pruned.

Key Takeaways

• Backtracking is essential for exploring all combinations while pruning invalid paths.
• The ability to reuse numbers is handled by keeping the same index `i` when a candidate is included.
• Moving to `i + 1` ensures that distinct candidates are considered for new branches.
• The base cases efficiently stop recursion when a target is met or exceeded.
• A `list(current_combination)` copy is crucial when adding to results to prevent modification by subsequent backtracking.