Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
A complete visual walkthrough of backtracking with element reuse — from brute force to optimal pruning.
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. 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.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
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: []
Constraints:
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates are distinct.1 <= target <= 40The naive approach would generate all possible subsets of every length, with repetition, then check which ones sum to the target. For candidates = [2, 3, 6, 7] and target = 7, we would enumerate an enormous number of combinations — most of them useless.
With unlimited reuse, the search space is infinite unless we prune intelligently. For example, we could keep picking 2 forever: [2, 2, 2, 2, ...] and never stop.
We need a systematic way to explore combinations without duplicates and with early termination when the running sum exceeds the target.
The trick is a classic backtracking pattern: at each step, we choose a candidate, add it to our current path, then recurse with a reduced target. After the recursive call returns, we undo the choice (backtrack) and try the next candidate.
In standard combination problems (no reuse), the recursive call starts from i + 1 to avoid picking the same element again. Here, we pass i (the same index) because the same number can be reused unlimited times.
Sorting first lets us prune early: once candidates[i] exceeds the remaining target, all subsequent candidates (which are larger) will too, so we can break immediately instead of continuing the loop.
Three rules govern the backtracking:
Let's trace the backtracking for candidates = [2, 3, 6, 7], target = 7. The sorted order is already [2, 3, 6, 7]. Each node shows the current path and remaining target.
Two solutions found: [2, 2, 3] and [7]. Notice how sorting + the break on overshoot aggressively prunes the tree. Without sorting, we would waste time exploring many more dead-end branches.
The start index parameter prevents generating duplicate combinations like [2, 3, 2] and [3, 2, 2] — once we move past candidate 2, we never go back to it. We only consider candidates at index start or later.
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(candidates); // Sort for early termination backtrack(candidates, target, 0, new ArrayList<>(), result); return result; } private void backtrack(int[] candidates, int remain, int start, List<Integer> path, List<List<Integer>> result) { if (remain == 0) { // Target reached — record solution result.add(new ArrayList<>(path)); return; } for (int i = start; i < candidates.length; i++) { if (candidates[i] > remain) // Prune: too large (and all after) break; path.add(candidates[i]); // Choose backtrack(candidates, remain - candidates[i], i, // ← NOT i+1: allow reuse path, result); path.remove(path.size() - 1); // Un-choose (backtrack) } } }
func combinationSum(candidates []int, target int) [][]int { sort.Ints(candidates) // Sort for early termination var result [][]int var backtrack func(remain, start int, path []int) backtrack = func(remain, start int, path []int) { if remain == 0 { // Target reached — record solution tmp := make([]int, len(path)) copy(tmp, path) result = append(result, tmp) return } for i := start; i < len(candidates); i++ { if candidates[i] > remain { // Prune: too large (and all after) break } path = append(path, candidates[i]) // Choose backtrack(remain-candidates[i], i, // ← NOT i+1: allow reuse path) path = path[:len(path)-1] // Un-choose (backtrack) } } backtrack(target, 0, nil) return result }
class Solution: def combination_sum(self, candidates: list[int], target: int) -> list[list[int]]: result: list[list[int]] = [] candidates.sort() # Sort for early termination self._backtrack(candidates, target, 0, [], result) return result def _backtrack(self, candidates: list[int], remain: int, start: int, path: list[int], result: list[list[int]]) -> None: if remain == 0: # Target reached — record solution result.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] > remain: # Prune: too large (and all after) break path.append(candidates[i]) # Choose self._backtrack(candidates, remain - candidates[i], i, # ← NOT i+1: allow reuse path, result) path.pop() # Un-choose (backtrack)
impl Solution { pub fn combination_sum(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> { candidates.sort(); // Sort for early termination let mut result = Vec::new(); Self::backtrack(&candidates, target, 0, &mut Vec::new(), &mut result); result } fn backtrack(candidates: &Vec<i32>, remain: i32, start: usize, path: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) { if remain == 0 { // Target reached — record solution result.push(path.clone()); return; } for i in start..candidates.len() { if candidates[i] > remain { // Prune: too large (and all after) break; } path.push(candidates[i]); // Choose Self::backtrack(candidates, remain - candidates[i], i, // ← NOT i+1: allow reuse path, result); path.pop(); // Un-choose (backtrack) } } }
function combinationSum(candidates: number[], target: number): number[][] { const result: number[][] = []; candidates.sort((a, b) => a - b); // Sort for early termination backtrack(candidates, target, 0, [], result); return result; } function backtrack(candidates: number[], remain: number, start: number, path: number[], result: number[][]): void { if (remain === 0) { // Target reached — record solution result.push([...path]); return; } for (let i = start; i < candidates.length; i++) { if (candidates[i] > remain) // Prune: too large (and all after) break; path.push(candidates[i]); // Choose backtrack(candidates, remain - candidates[i], i, // ← NOT i+1: allow reuse path, result); path.pop(); // Un-choose (backtrack) } }
Enter candidates and a target, then step through the backtracking tree to see how combinations are built and pruned.
Where n is the number of candidates, T is the target value, and min is the smallest candidate. The maximum recursion depth is T/min (picking the smallest element repeatedly). At each level, we branch up to n ways. Space is O(T/min) for the recursion stack and current path.
Without sorting or pruning, the recursion tree branches n ways at each level and can reach depth T (picking 1 repeatedly). Dead-end branches that overshoot the target are only detected after the recursive call, wasting O(nT) work.
Sorting candidates enables a break when candidates[i] > remain, cutting off all larger candidates at once. Max depth is T/min (smallest candidate repeated). The start-index parameter prevents duplicate orderings like [2,3] and [3,2].
Sorting candidates and breaking early when the sum exceeds the target dramatically prunes the search tree. Without sorting, we would explore dead-end branches that overshoot the target. With sorting, once candidates[i] > remain, all subsequent candidates are larger and can be skipped entirely.
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.