Combination Sum LeetCode 39 — Backtracking

LeetCode 39 — Combination Sum — gives you an array of distinct positive integers called candidates and a target integer. You must return all unique combinations of candidates that sum to the target. Each number in candidates may be used an unlimited number of times in a combination. The solution set must not contain duplicate combinations.

For example, given candidates = [2, 3, 6, 7] and target = 7, the output is [[2, 2, 3], [7]]. The combination [2, 2, 3] uses 2 twice and 3 once; [7] uses 7 once. There is no other way to reach 7 using elements from the array with unlimited repetition. The order within a combination does not matter — [2, 3, 2] and [2, 2, 3] are considered the same combination.

The problem requires systematic enumeration of all valid combinations without generating duplicates. A brute-force approach that tries all multisets would be extremely slow. Backtracking with careful index management is the standard efficient solution.

The backtracking approach explores a decision tree where at each node you choose one candidate from a start index onward and subtract it from the remaining target. If the remaining target reaches exactly 0, you have found a valid combination and record it. If the remaining target goes below 0, the current path exceeds the target and you prune immediately without recursing further.

The key detail is that when recursing after choosing candidates[i], you pass i as the new start index — not i + 1. This allows the same element to be chosen again in the next recursive call, implementing unlimited reuse. The current path (built as a list) accumulates chosen elements, and you pop the last element when backtracking to restore state for the next branch.

The general template is: for each index from start to end, add candidates[i] to the path, recurse with remaining = remaining - candidates[i] and new_start = i, then remove candidates[i] from the path. Check remaining <= 0 before recursing (if 0, record; if negative, break or continue).

Even though each candidate appears only once in the input array, combinations like [2, 2, 3] can be formed in multiple orders: you could pick 2, then 2, then 3; or 2, then 3, then 2; or 3, then 2, then 2. Without constraints, the backtracking would generate all three orderings as separate combinations — but they represent the same set and should appear only once in the output.

The solution is to start each recursive call from the current index, never going back to earlier indices. When you pick candidates[i], the next recursive call starts at index i (not 0). This means in any path through the decision tree, the chosen indices are non-decreasing. You can only pick the same element again or move to a later element — never revisit an earlier one.

This constraint on the start index is the complete solution to deduplication. It ensures that [2, 2, 3] is generated only via the path "pick index 0, pick index 0, pick index 1" and never via "pick index 1, then go back to index 0 twice". No sorting or visited-set is required purely for deduplication — though sorting helps with pruning.

Sorting the candidates array before running the backtracking algorithm enables a powerful optimization: early termination of the inner loop using break instead of continue. After sorting, candidates are in ascending order. When you encounter a candidate that is larger than the remaining target, every subsequent candidate will also be larger (since the array is sorted), so none of them can contribute to a valid combination.

Without sorting, if a candidate exceeds the remaining target you must use continue to skip it and check the next one — there might be a smaller candidate later. With sorting, candidates[i] > remaining means the entire rest of the loop is useless, so you can break immediately. This prunes not just one candidate but the entire tail of the sorted array, saving significant work on larger inputs.

The practical impact is substantial: for target = 7 and candidates = [2, 3, 6, 7], once you have remaining = 1, sorted order means candidates[0] = 2 > 1 causes an immediate break rather than checking 3, 6, and 7 individually. This effect compounds across every node in the decision tree, producing a measurable speedup on inputs with many large candidates.

To trace through a concrete example, take candidates = [2, 3, 6, 7] (sorted) and target = 7. The root node has remaining = 7 and start = 0. It branches into four choices: pick 2 (remaining 5), pick 3 (remaining 4), pick 6 (remaining 1), pick 7 (remaining 0). The branch where we pick 7 immediately yields the combination [7] — remaining is exactly 0.

The branch where we first pick 2 (remaining = 5, start = 0) branches again: pick 2 (remaining 3, start = 0), pick 3 (remaining 2, start = 1), pick 6 (remaining -1, prune), pick 7 (remaining -2, prune). The sub-branch "pick 2 then pick 2" (remaining = 3, start = 0) branches: pick 2 (remaining 1, start = 0 — then 2 > 1 breaks), pick 3 (remaining 0) — yields [2, 2, 3]. The path [2, 3, ...] sub-branch reaches remaining 2 from start 1, picks 3 (remaining -1, prune by break). No further paths from the first "pick 2" yield valid combinations.

Total valid combinations found: [2, 2, 3] via path (2, 2, 3) and [7] via path (7). The decision tree has been pruned extensively — all branches where the running total exceeded 7 were cut immediately after the sort-based break triggered. This matches the expected output for this example.

In Python, sort candidates first. The combinationSum function initializes an empty results list and calls backtrack(0, [], target). The backtrack(start, path, remaining) function checks if remaining == 0 and appends path[:] to results. Otherwise, it loops over i from start to len(candidates) - 1, breaks if candidates[i] > remaining, appends candidates[i] to path, recurses with backtrack(i, path, remaining - candidates[i]), then pops path. Time complexity is O(n^(t/m)) where t is the target and m is the minimum candidate value — this bounds the maximum depth and branching factor. Space complexity is O(t/m) for the recursion stack depth.

In Java, Arrays.sort(candidates) first. The public List<List<Integer>> combinationSum(int[] candidates, int target) method initializes a List<List<Integer>> result and calls backtrack(candidates, target, 0, new ArrayList<>(), result). The private void backtrack method checks if remaining == 0, adds new ArrayList<>(current) to result, and returns. Otherwise, it loops from start, breaks if candidates[i] > remaining, adds to current, recurses with i (not i+1) for unlimited reuse, then removes the last element from current.

Both implementations follow the same structure: sort, recurse with same index for reuse, break on over-target, pop on backtrack. There is no memoization — each path is unique because of the non-decreasing index constraint. The algorithm is pure backtracking with constraint-based pruning, not dynamic programming.

Combination Sum IV (LeetCode 377) asks for the number of ways to reach a target — not all combinations, but a count where order matters. This converts the problem from backtracking enumeration to dynamic programming. Understanding Combination Sum 39 first helps you see why DP works for counting but not for enumeration of actual combinations.

N-Queens (LeetCode 51) and Palindrome Partitioning (LeetCode 131) are canonical backtracking problems that use the same "make choice, recurse, undo choice" template. N-Queens adds conflict tracking with sets; Palindrome Partitioning adds a string validity check at each step. The backtracking skeleton from Combination Sum applies directly to both with minor adaptations.

Permutations (LeetCode 46), Subsets (LeetCode 78), and the broader backtracking family — word search, generate parentheses, letter combinations — all share the same recursive template. Mastering Combination Sum 39 provides a clean mental model for the unlimited-reuse pattern that contrasts with Combination Sum II (used-once) and Permutations (all orderings). Together these three problems cover the core variants of combinatorial enumeration.