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 value. A key characteristic is that the same candidate number can be chosen multiple times.

The Challenge of Brute Force

A naive brute-force approach, which attempts every possible combination, quickly becomes unmanageable. With unlimited reuse of candidates, the number of potential combinations is infinite, leading to an extremely inefficient search that explores millions of irrelevant paths.

Systematic Search with Backtracking

To efficiently solve this, we employ a systematic search strategy based on backtracking. This method models the problem as exploring paths in a decision tree. At each step, we consider adding a candidate number to our current combination. This choice subtracts the candidate's value from our remaining target.

Exploring and Undoing Choices

Backtracking works by making a choice, exploring all possibilities stemming from that choice, and then "undoing" the choice to explore alternative paths. For example, if we choose `2`, we then recursively try to find combinations for the reduced target. After exhausting all paths with `2`, we backtrack to try a different candidate.

Pruning Inefficient Paths

An essential optimization is pruning. If the sum of numbers in our current path exceeds the target, there's no need to continue down that path, as adding more positive numbers will only increase the sum further. We immediately stop exploring that branch, significantly reducing the search space.

Success Condition

A combination is considered successful when the remaining target value reaches zero. At this point, the current path represents a valid combination, which is then recorded. The algorithm then backtracks to find other unique combinations.

function combinationSum(candidates, target):
    results = []
    current_path = []

    function backtrack(remaining_target, start_index):
        if remaining_target == 0:
            results.add(list(current_path)) # Found a valid combination
            return
        if remaining_target < 0:
            return # Prune: current sum exceeds target

        for i from start_index to candidates.length - 1:
            current_path.add(candidates[i])
            # Allow reuse of the same element, so pass 'i' not 'i + 1'
            backtrack(remaining_target - candidates[i], i)
            current_path.remove_last() # Backtrack: undo the choice

    backtrack(target, 0)
    return results

Key Takeaways

• Backtracking systematically explores all potential combinations.
• Decision trees visually represent the choices made at each step.
• Pruning optimizes the search by discarding paths where the sum exceeds the target.
• Unlimited reuse of candidate numbers is a defining feature.
• The algorithm finds all unique combinations that sum to the target.