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

For every candidate, we can either include it in the combination or exclude it and move to the next candidate.

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

The problem is naturally recursive in nature. At every step, we are trying to solve the same problem for a reduced target.

Recursive Include-Exclude Pattern

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(currentCombination.clone());
    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;
}

Visualization

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.