Combination Sum

The problem

Given distinct positive integers candidates and a target, return all unique combinations where the chosen numbers sum to the target. The same number may be used unlimited times. Combinations differing only in order count as the same (so [2, 3] and [3, 2] are one answer).

Example: candidates = [2, 3, 6, 7], target = 7 → [[2, 2, 3], [7]].

Two wrinkles beyond plain subsets: numbers are reusable, and we must avoid emitting the same multiset in different orders.

Approach 1 — Naive DFS over all candidates (why it duplicates)

If every recursive call may pick any candidate, the paths 2 → 2 → 3, 2 → 3 → 2, and 3 → 2 → 2 all reach the same combination — you'd need to sort each result and deduplicate with a set. Wasteful and messy.

The fix is an ordering rule: each call may only pick candidates at or after its start index. Once you move past a candidate, you never return to it — so every combination is generated exactly once, in non-decreasing candidate order.

Approach 2 — Backtracking with a start index

function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b) // enables early pruning
  const result = []
  const path = []

  function backtrack(start, remaining) {
    if (remaining === 0) {
      result.push([...path])
      return
    }

    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break // sorted → everything after is bigger too

      path.push(candidates[i])
      backtrack(i, remaining - candidates[i]) // i, NOT i + 1 — reuse allowed
      path.pop()
    }
  }

  backtrack(0, target)
  return result
}

Time: exponential in the worst case (it's an enumeration problem — the output itself can be huge); pruning cuts real workloads dramatically. Space: O(target / min(candidates)) recursion depth.

The two indexes to internalize:

• backtrack(i, ...) — passing i (not i + 1) is what allows reusing the same candidate.
• The loop starting at start is what prevents [3, 2, 2]-style reorderings of [2, 2, 3].

Dry run

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

Result: [[2, 2, 3], [7]]. Notice [3, 2, 2] was never even attempted — the start index makes that branch unreachable.

Edge cases

• target smaller than every candidate → [].
• A candidate equal to the target → single-element combination, found immediately.
• The guaranteed-positive candidates are what make remaining strictly decrease — with zeros or negatives the recursion could never terminate without extra guards.
• Variant map: Combination Sum II (LC 40) = duplicates in input, each used once → pass i + 1 and skip equal neighbors; Combination Sum III (LC 216) = fixed count k → add a length check.