TL;DR
Backtracking with a start index (reuse allowed) plus sort-and-prune — O(k · 2^(t/m)) time in the worst case (k = average combination length, t = target, m = smallest candidate), O(t/m) recursion space beyond the output.
Approach 1 — Brute force
Recursively try every candidate at every step with no ordering discipline, collect sequences that hit the target, and deduplicate at the end by sorting each sequence and putting it in a set.
from typing import List
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
found: set[tuple[int, ...]] = set()
def explore(remaining: int, path: List[int]) -> None:
if remaining == 0:
found.add(tuple(sorted(path)))
return
if remaining < 0:
return
for c in candidates: # any candidate, any time
path.append(c)
explore(remaining - c, path)
path.pop()
explore(target, [])
return [list(t) for t in found]
Complexity: O(n^(t/m)) time (n candidates chosen at up to t/m levels), plus sorting every hit; O(t/m) recursion depth. It generates every ordering of every combination — [2,2,3] is found 3 times as [2,2,3], [2,3,2], [3,2,2] — so the duplicate orderings make it infeasible well before n = 30.
Approach 2 — Backtracking with a start index
The insight: duplicates like [2,3] vs [3,2] exist only because the brute force lets you pick candidates in any order. Impose a canonical order: each recursive call receives a start index and may only use candidates[start:]. Because reuse is allowed, picking candidates[i] recurses with start = i (not i + 1). Every combination is now generated exactly once, in non-decreasing index order — no dedup set needed. This is classic backtracking: depth-first search over partial solutions that abandons (“backtracks from”) any partial path that can no longer lead to a valid answer.
from typing import List
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
result: List[List[int]] = []
path: List[int] = []
def backtrack(start: int, remaining: int) -> None:
if remaining == 0:
result.append(path.copy())
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining:
continue # this pick overshoots; try the next
path.append(c)
backtrack(i, remaining - c) # i, not i + 1: reuse allowed
path.pop()
backtrack(0, target)
return result
Walkthrough on candidates = [2,3,6,7], target = 7:
- Pick
2 (remaining 5) → pick 2 (remaining 3) → pick 2 (remaining 1): every candidate > 1, dead end, pop back to remaining 3.
- At remaining 3, next option is
3 → remaining 0 → record [2,2,3]. Pop back.
- At remaining 5, trying
3 leaves 2, and no candidate from index 1 onward is <= 2 → dead end. 6, 7 overshoot 5.
- Back at the top: pick
3 (remaining 4) → 3 leaves 1, dead end; 6, 7 overshoot. Pick 6 (remaining 1): dead end. Pick 7 → remaining 0 → record [7].
- Result:
[[2,2,3],[7]].
The search tree (each node is the remaining target; edge labels are the picked candidate):
flowchart TD
R["remaining 7"]
R -->|"pick 2"| A["remaining 5"]
R -->|"pick 3"| B["remaining 4"]
R -->|"pick 6"| C["remaining 1 — dead"]
R -->|"pick 7"| D["remaining 0 — record [7]"]
A -->|"pick 2"| A1["remaining 3"]
A -->|"pick 3"| A2["remaining 2 — dead"]
A1 -->|"pick 2"| A1a["remaining 1 — dead"]
A1 -->|"pick 3"| A1b["remaining 0 — record [2,2,3]"]
B -->|"pick 3"| B1["remaining 1 — dead"]
Complexity: the recursion tree has branching factor up to n and depth up to t/m, so O(n^(t/m)) worst case, but each combination is produced exactly once and dead branches stop at the first overshoot. Space O(t/m) for the path/recursion (output excluded).
Approach 3 — Sort first, prune the whole loop
The insight: if the candidates are sorted ascending and candidates[i] already overshoots the remaining target, every later candidate overshoots too — so you can break out of the loop instead of continue, discarding all remaining siblings at once.
from typing import List
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
candidates = sorted(candidates)
result: List[List[int]] = []
path: List[int] = []
def backtrack(start: int, remaining: int) -> None:
if remaining == 0:
result.append(path.copy())
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining:
break # sorted: everything after also overshoots
path.append(c)
backtrack(i, remaining - c)
path.pop()
backtrack(0, target)
return result
Walkthrough on candidates = [2,3,5], target = 8 (already sorted):
| path | remaining | action |
|---|
[2,2,2,2] | 0 | record |
[2,2,2] + try 3 | 2 − 3 < 0 | 3 > 2 → break, pop |
[2,3,3] | 0 | record |
[2,5] | 1 | 2 > 1 → break at once, pop |
[3,5] | 0 | record |
[5,5] | — | 5 > 3 → break |
Result: [[2,2,2,2],[2,3,3],[3,5]] — same asymptotic bound as Approach 2, but the break prunes whole sibling groups, which matters as n grows. (A dynamic-programming alternative exists — build the combination lists for every value 0..target, unbounded-knapsack style — but it materializes combination lists for intermediate targets you never report, so backtracking is the standard answer here.)
Common pitfalls
- Recursing with
i + 1 after picking candidates[i] — that forbids reuse and silently turns this into Combination Sum II.
- Appending
path itself instead of path.copy() — every recorded answer then mutates as the search continues, and you end with a list of empty lists.
- Using
continue where sorted input allows break — correct but forfeits the cheap prune.
- Deduplicating with a set of sorted tuples instead of fixing the search order — it masks the real bug (an unordered search) and adds an O(k log k) cost per hit.
Pattern takeaway
The backtracking template is: choose → recurse → un-choose (append / call / pop), recording the path at valid leaves. The order-of-generation trick is the part to carry forward: when answers are sets (order doesn’t matter) but your search produces sequences, don’t dedupe afterward — constrain the search with a start index so each set is generated in exactly one canonical order. Whether the recursive call gets i or i + 1 is precisely the “with reuse / without reuse” switch.