Combination Sum

LeetCode 39: Combination Sum Solution & Explanation

Problem Overview

TL;DR: To solve LeetCode 39, use a backtracking algorithm that builds combinations incrementally, allowing the reuse of elements by maintaining the current index during recursion, and pruning paths that exceed the target sum.

The Combination Sum problem asks us to find all unique combinations of numbers from a given array of distinct integers (candidates) that sum up to a specific target. A critical feature of this problem is that we can use the same number from the candidates array an unlimited number of times. The order of numbers in the output combinations does not matter, but the combinations themselves must be unique.

This is a classic algorithmic challenge often encountered in technical interviews at top tech companies. It tests your ability to manage state space trees and implement recursion effectively.

Brute Force Approach for Combination Sum

A naive brute force approach would attempt to generate every possible subset of numbers, including subsets with repeated elements, and check if their sum equals the target. Since we can reuse numbers, the length of a potential combination is theoretically bounded only by target / min(candidates).

To implement this naively, one might write a recursive function that blindly adds numbers to a list until the sum equals or exceeds the target, without a structured strategy to avoid duplicate combinations (permutations of the same set) or optimize the search.

Pseudo-code for Naive Approach

function getAllSubsets(current_path):
    if sum(current_path) == target:
        add current_path to results
        return
    if sum(current_path) > target:
        return

    for number in candidates:
        // Naively tries every number at every step
        // This generates [2, 3] and [3, 2] as separate answers
        getAllSubsets(current_path + [number])

Why this fails

1. Duplicate Combinations: The brute force method treats [2, 2, 3] and [2, 3, 2] as different outcomes. Since the problem asks for unique combinations, this requires an expensive post-processing step to filter duplicates.
2. Inefficiency: Without a strategy to restrict the search space (e.g., enforcing an order of element selection), the branching factor remains maximum at every depth level. This results in significant redundant computation.

Algorithm Strategy: Backtracking Patterns

We implement the solution using a recursive backtracking function. The function maintains the current state of our search.

State Variables

1. startIndex: The index in candidates where we begin our search for the current recursive step. This enforces the "no looking back" constraint.
2. currentPath: A list tracking the numbers selected so far.
3. currentSum: The running total of numbers in currentPath.

Constraints and Boundaries

1. Base Case (Success): If currentSum == target, we have found a valid combination. We make a deep copy of currentPath and add it to our result list.
2. Base Case (Failure): If currentSum > target, this path is invalid. We return immediately (prune).
3. Recursive Step: We iterate through candidates starting from startIndex.
   • For each candidate, we add it to currentPath and add its value to currentSum.
   • We make a recursive call. Crucially, we pass the same index i into the recursion (not i + 1). This allows the algorithm to reuse the current number.
   • After the recursive call returns, we backtrack: remove the last added number from currentPath and subtract its value from currentSum to explore the next candidate.

Execution Flow

Let's trace the execution for candidates = [2, 3, 6, 7], target = 7.

1. Start: backtrack(start=0, path=[], sum=0)
2. Iterate i=0 (Value 2):
   • Add 2. Path: [2], Sum: 2.
   • Recurse backtrack(start=0). (Allow reuse of 2)
3. Inside Recursion (Path [2]):
   • Iterate i=0 (Value 2):
     • Add 2. Path: [2, 2], Sum: 4.
     • Recurse backtrack(start=0).
4. Inside Recursion (Path [2, 2]):
   • Iterate i=0 (Value 2):
     • Add 2. Path: [2, 2, 2], Sum: 6.
     • Recurse backtrack(start=0).
5. Inside Recursion (Path [2, 2, 2]):
   • Iterate i=0 (Value 2):
     • Add 2. Path: [2, 2, 2, 2], Sum: 8.
     • Prune: Sum > Target. Backtrack. Pop 2.
   • Iterate i=1 (Value 3):
     • Add 3. Path: [2, 2, 2, 3], Sum: 9.
     • Prune: Sum > Target. Backtrack. Pop 3.
   • ... (6 and 7 also prune) ...
   • Return to previous level.
6. Back at Path [2, 2], Sum 4:
   • We finished i=0 (Value 2). Now i=1 (Value 3).
   • Add 3. Path: [2, 2, 3], Sum: 7.
   • Success: Sum == Target. Add [2, 2, 3] to results.
   • Backtrack. Pop 3.
   • ... Continue exploring ...

This systematic depth-first search ensures we find [2, 2, 3] via the path of picking 2, then 2, then 3. We will never find [2, 3, 2] because once we move to index 1 (Value 3), we never iterate back to index 0 (Value 2).

Proof of Correctness

The correctness of this Backtracking approach rests on two pillars:

1. Completeness: By iterating through every candidate starting from the current startIndex and allowing reuse, we explore every possible combination of numbers that could sum to target. The recursion tree covers the entire valid search space.
2. Uniqueness: The startIndex parameter enforces an ordering constraint. A number at index j can only be followed by numbers at indices k >= j. This effectively sorts the indices used in any combination. Since a set of numbers has exactly one sorted representation, we are guaranteed to generate each unique combination exactly once.

Pattern Reuse Notes

The Backtracking - Combination Sum pattern is highly transferable. Understanding how to manipulate the startIndex and recursion logic allows you to solve variations efficiently:

• LeetCode 40: Combination Sum II: The pattern is nearly identical, but numbers cannot be reused. The fix is simply passing i + 1 instead of i in the recursive call, along with logic to skip duplicate candidates in the sorted array.

Reference Implementation

C++ Solution for LeetCode 39

1class Solution {
2public:
3    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
4        vector<vector<int>> result;
5        vector<int> currentPath;
6        backtrack(candidates, target, 0, 0, currentPath, result);
7        return result;
8    }
9
10private:
11    void backtrack(const vector<int>& candidates, int target, int currentSum, int startIndex, 
12                   vector<int>& currentPath, vector<vector<int>>& result) {
13        
14        // Base Case: Success
15        if (currentSum == target) {
16            result.push_back(currentPath);
17            return;
18        }
19        
20        // Base Case: Failure (Pruning)
21        if (currentSum > target) {
22            return;
23        }
24        
25        // Recursive Step
26        for (int i = startIndex; i < candidates.size(); ++i) {
27            currentPath.push_back(candidates[i]);
28            // Pass 'i' as startIndex to allow reusing the same element
29            backtrack(candidates, target, currentSum + candidates[i], i, currentPath, result);
30            // Backtrack: remove the last element to explore other possibilities
31            currentPath.pop_back();
32        }
33    }
34};

Java Solution for LeetCode 39

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public List<List<Integer>> combinationSum(int[] candidates, int target) {
6        List<List<Integer>> result = new ArrayList<>();
7        List<Integer> currentPath = new ArrayList<>();
8        backtrack(candidates, target, 0, 0, currentPath, result);
9        return result;
10    }
11
12    private void backtrack(int[] candidates, int target, int currentSum, int startIndex, 
13                           List<Integer> currentPath, List<List<Integer>> result) {
14        
15        // Base Case: Success
16        if (currentSum == target) {
17            // Must create a new ArrayList because currentPath is a reference
18            result.add(new ArrayList<>(currentPath));
19            return;
20        }
21
22        // Base Case: Failure (Pruning)
23        if (currentSum > target) {
24            return;
25        }
26
27        // Recursive Step
28        for (int i = startIndex; i < candidates.length; i++) {
29            currentPath.add(candidates[i]);
30            // Pass 'i' as startIndex to allow reusing the same element
31            backtrack(candidates, target, currentSum + candidates[i], i, currentPath, result);
32            // Backtrack: remove the last element
33            currentPath.remove(currentPath.size() - 1);
34        }
35    }
36}

Python Solution for LeetCode 39

1from typing import List
2
3class Solution:
4    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
5        result = []
6        
7        def backtrack(start_index: int, current_sum: int, current_path: List[int]):
8            # Base Case: Success
9            if current_sum == target:
10                result.append(current_path[:]) # Append a copy of the path
11                return
12            
13            # Base Case: Failure (Pruning)
14            if current_sum > target:
15                return
16            
17            # Recursive Step
18            for i in range(start_index, len(candidates)):
19                num = candidates[i]
20                current_path.append(num)
21                # Pass 'i' to allow reusing the same element
22                backtrack(i, current_sum + num, current_path)
23                # Backtrack
24                current_path.pop()
25        
26        backtrack(0, 0, [])
27        return result