Combination Sum

Given an array of distinct candidate numbers and a target, return all unique combinations where the chosen numbers sum to the target. Each candidate may be used unlimited times. Combinations can be returned in any order.

Why this is worth learning

Positive reusable candidates turn the search into a nondecreasing sequence of choices. Sorting lets the first value above the remaining target stop the whole loop, not just one branch.

Before coding: one-minute experiment

For candidates [2,3,6,7] and target 7, why does the branch choosing 2 recurse at its current index rather than the next index?

Function signature

func CombinationSum(candidates []int, target int) [][]int

Inputs / outputs

• candidates: distinct positive integers.
• target: positive integer target sum.
• Return: all unique combinations that sum to target.

Example

candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Constraints

• 1 <= len(candidates) <= 30
• 1 <= target <= 500

Core idea (near-solution)

One complete small-instance model chooses a nonnegative multiplicity for every candidate, then checks the weighted sum. A path search expresses the same choices incrementally. For candidates [2,3], target 7, [2,2,3] is a solution but its reorderings are not new solutions. Nondecreasing candidate indices select one representation, and reusing the current index permits repeated 2s. Positive values make the remaining target a decreasing measure.

Backtrack over candidates in non-decreasing order. Reusing the same index avoids permutation duplicates.

Invariant: path is a non-decreasing sequence of candidates whose sum is target - remain.

Algorithm (step-by-step)

1. Sort candidates so both pruning and nondecreasing result rows follow from index order. The reference sorts in place; a copy is also possible if the caller needs the original order.
2. DFS dfs(start, remain):
   • If remain == 0, record a copy of path and return.
   • For each index i from start to end:
     • If candidates[i] > remain, break; every later sorted candidate is also too large.
     • Choose candidates[i], recurse with dfs(i, remain - candidates[i]) (reuse allowed).
     • Backtrack.
3. Return all recorded combinations.

Correctness sketch

The path sum plus remaining equals the original target, and candidate indices along the path never decrease. Selecting index i and recursing again at i permits reuse while excluding reorderings of the same multiset. Since candidates are distinct and positive, every valid multiset has one sorted representation, and each recursive step strictly decreases remaining. The branch reaching remaining zero is exactly a valid sum. Once a sorted candidate exceeds remaining, all later candidates do too, so none can complete the path. This proves termination, completeness, and duplicate avoidance under the positive-distinct preconditions.

Trace (hand walkthrough)

Example input:
candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Walk:
- take 2 -> remain 5; take 2 -> remain 3; take 3 -> [2,2,3]
- take 7 directly -> [7]

Pitfalls to avoid

• Using i+1 in recursion (would forbid reuse).
• Failing to copy path when adding to results.
• Producing duplicate permutations by resetting start to 0.

Debugging lens

Zero candidates destroy the decreasing-remaining argument; negative candidates destroy sorted upper-bound pruning. They are outside the contract. The reference sorts candidates in place, so copy them when order must be retained.

Complexity

Let C be candidate count and d=floor(target/minCandidate). Sorting costs O(C log C). Search is output-sensitive and exponential; a loose upper bound is O(C^(d+1)+d R) for R results, including copied paths. Auxiliary path/recursion space is O(d), excluding sorting stack and output.

Implementation notes (Go)

• Store results as [][]int and copy path with append([]int(nil), path...).
• Sorting allows early pruning and smaller search.

Contract precision

Candidates are distinct positive integers and target is positive. The reference mutates the candidate slice by sorting it; each result row is nondecreasing, and the order of result rows is unrestricted.

Reconstruction checkpoint

For candidates [2,3,6,7] and target 7, why does the branch choosing 2 recurse at its current index rather than the next index?

Return to Backtracking · Module quiz