Combination Sum - Complete Backtracking Guide

Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen from candidates an unlimited number of times.

Example:

• candidates = [2,3,6,7], target = 7
• Output: [[2,2,3], [7]]

Understanding the Core Concept

Combination Sum is a classic Backtracking problem. Unlike standard recursion where you might explore all paths, backtracking in this context involves:

1. Exploration: Trying to include a number from the candidates list.
2. Constraint Checking: Ensuring the current sum does not exceed the target.
3. Pruning: Stopping the recursion early if the current path cannot lead to a valid solution.
4. Backtracking: Undoing the last choice (removing the number) to explore other possibilities.

The "Unlimited Times" Constraint

The most critical distinction in this problem is that you can reuse the same number. This means when you make a recursive call, you typically pass the same index (or a start index) to the function, rather than moving to the next index. This allows the algorithm to stay on the same number and try adding it again.

Algorithm Strategy

Step 1: Sorting

First, sort the candidates array. Sorting is not strictly required for correctness but is crucial for optimization. It allows us to use pruning (breaking out of loops early) when the current number makes the sum exceed the target.

Step 2: The Backtracking Function

We define a recursive function backtrack(startIndex, currentCombination, currentSum):

• startIndex: The index from which we start considering numbers. This prevents us from generating duplicate combinations (e.g., [2,3] and [3,2] are the same combination) and ensures we only use numbers that come after or at the current position.
• currentCombination: An array storing the numbers selected so far.
• currentSum: The sum of the numbers in currentCombination.

Step 3: Base Case

If currentSum === target, we have found a valid combination. We push a copy of currentCombination to our result list.

Step 4: Recursive Step

We iterate through the candidates starting from startIndex:

1. Pruning: If currentSum + candidates[i] > target, we break the loop. Since the array is sorted, all subsequent numbers will be larger, and the sum will only increase.
2. Include: Add candidates[i] to currentCombination and currentSum.
3. Recurse: Call backtrack(i, currentCombination, currentSum). Notice we pass i (not i + 1), allowing the reuse of the current number.
4. Backtrack: Remove the last element from currentCombination (undo the choice) and subtract candidates[i] from currentSum before moving to the next iteration.

Code Implementation (TypeScript)

function combinationSum(candidates: number[], target: number): number[][] {
    const result: number[][] = [];
    // Sort to enable pruning
    candidates.sort((a, b) => a - b);
    
    function backtrack(startIndex: number, currentCombination: number[], currentSum: number) {
        // Base Case: Found a valid combination
        if (currentSum === target) {
            result.push([...currentCombination]);
            return;
        }
        
        for (let i = startIndex; i < candidates.length; i++) {
            const num = candidates[i];
            
            // Pruning: If adding this number exceeds the target, stop
            if (currentSum + num > target) {
                break;
            }
            
            // Include the number
            currentCombination.push(num);
            
            // RECURSE: Pass 'i' to allow reuse of the same number
            backtrack(i, currentCombination, currentSum + num);
            
            // Backtrack: Remove the number to try the next candidate
            currentCombination.pop();
        }
    }
    
    backtrack(0, [], 0);
    return result;
}

Complexity Analysis

Time Complexity: $O(N^{T/M + 1})$

This is a theoretical upper bound. Here:

• $N$ is the number of candidates.
• $T$ is the target sum.
• $M$ is the smallest number in the candidates array.

The complexity arises because in the worst case, the recursion tree can grow exponentially. However, due to pruning, the actual runtime is often much faster.

Space Complexity: $O(T/M)$

• Result Storage: We store all valid combinations. In the worst case, the depth of the recursion tree is $T/M$ (the number of times we can add the smallest number to reach the target).
• Recursion Stack: The call stack depth is also $O(T/M)$.

Common Pitfalls & Best Practices

1. Passing the Wrong Index: A common mistake is passing i + 1 to the recursive call. This would prevent reusing the same number, turning the problem into a standard subset sum problem rather than Combination Sum.
2. Copying the Array: Always push a copy ([...currentCombination]) to the result array. If you push the reference directly, it will be modified later when the array is popped during backtracking.
3. Ignoring Sorting: If you skip sorting, you cannot use pruning. This leads to unnecessary recursive calls that exceed the target, significantly slowing down the solution for large inputs.
4. Infinite Loops: Ensure your base case (currentSum === target) is checked before the loop or at the very beginning of the function to prevent infinite recursion if the target is 0 or negative (though the problem constraints usually ensure positive targets).

Real-World Applications

• Resource Allocation: Assigning tasks or resources to a budget where a specific resource can be used multiple times.
• Scheduling: Finding time slots that fit a specific duration constraint.
• Game Development: Calculating possible scores or moves in a turn-based game where moves can be repeated.