Data Structures & Algorithms (Backtracking): Combination Sum

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.

NOTE: You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Playground: Leetcode 39

Key Observation

The problem is naturally recursive in nature. For every candidate, we can either include it in the combination or exclude it and move to the next candidate.

At every step, we are trying to solve the same problem for a subset of candidates and a reduced target.

NOTE: Ordering is not important in combinations. For example, [2,2,3] is same as [3,2,2] and [2,3,2].

Approach 1: Include - Exclude

Use recursion to process one candidate at a time. At each step, make a decision for a specific element, either include it in the current combination or exclude it and move to the next element.

Hypothesis

Let F(currentIndex, candidates, target) be a function that generates all unique combinations whose sum equal to target by exploring every feasible choice from the range: [index, candidates.length - 1].

NOTE: Maintain a (List<Integer> currentCombination) to track the current combination being built during recursion, and a (List<List<Integer>> allCombinations) to store all valid combinations that meet the target sum.

Recursive Steps

// Step 1: Include the integer at index = currentIndex
currentCombination.add(candidates[currentIndex]);
F(currentIndex, candidates, target - candidates[currentIndex]);

// Step 2: Exclude the integer at index = currentIndex
currentCombination.remove(currentCombination.size() - 1);
F(currentIndex + 1, candidates, target);

Base Conditions

Since we reduce the target at each recursive call, reaching target == 0 indicates that the sum of the currentCombination exactly matches the original target, and hence we have found a valid combination.

if (target == 0) {
    allCombinations.add(new ArrayList<>(currentCombination)); // save the clone of the currentCombination
    return;
}

If we reach target < 0, it means the currentCombination has exceeded the required sum, and any further exploration will only increase the sum, so this path cannot lead to a valid solution.

if (target < 0) {
    return;
}

Time Complexity

At each recursive call we make two choices:

1. include candidates[currentIndex] (stay at same index, reduce target) or
2. exclude it (advance index, keep target).

The recursion tree is binary. The maximum depth of the tree is determined by how many times we can include the smallest candidate before the target hits zero or goes negative:

max depth ≈ T / M, where T = target value and M = minimum value in candidates.

A binary tree of height T/M has at most 2^{T/M} nodes, hence, overall time complexity = O(2^{T/M}).

Space Complexity

Each recursive call reduces the target by at least the smallest candidate value, so the maximum depth of the recursion tree is approximately T/M, where T is the target and M is the minimum candidate. As a result, both the recursion stack and the current combination list require O(T / M) space.

Apart from this auxiliary space, additional memory is used to store the final results, which can grow exponentially depending on the number of valid combinations, but the core working space of the algorithm remains linear in terms of recursion depth.

Optimization

In the include - exclude pattern, each recursion level focuses on making a decision about a single element (whether to pick it or skip it). However, in this problem, instead of restricting ourselves to one element per level, we can directly explore all available candidates at each step.

Using a for-loop could help us eliminate redundant exclusion calls by implicitly handling the skip decisions through index progression, instead of explicitly making separate recursive calls to exclude each element.

Approach 2: Explore All Feasible Choices

At each recursive step, rather than making a binary decision of inluding or excluding the current element, run a loop to explore all available candidates.

Hypothesis

Let F(currentIndex, candidates, target) be a function that generates all unique combinations whose sum equals target by exploring all feasible choices from the range [currentIndex, candidates.length - 1].

Recursive Steps

for(int i = currentIndex; i < candidates.length - 1; i++) {
    // Step 1: Include the current candidate
    currentCombination.add(candidates[i]);

    // Step 2: Recurse (reuse allowed - stay at the same index i)
    F(i, candidates, target - candidates[i]);

    // Step 3: Backtrack (undo choice)
    currentCombination.remove(currentCombination.size() - 1);
}

Base Conditions

same as the include - exclude approach

Time Complexity

In the worst case, we'll keep picking the smallest element at each level and we run a loop for almost N times.

An N-ary tree of height T/M has at most N^{T/M} nodes, where T = target value and M = minimum value in candidates. Hence, the overall time complexity = O(N^{T/M}).

NOTE: Even though N^(T/M) looks worse than 2^(T/M), the loop approach is faster in practice because it avoids unnecessary branches.

Space Complexity

Considering each recursive call reduces the target T by at least the smallest candidate value M, both the recursion stack and the current combination list will consume O(T / M) space.