Find all unique combinations of candidates that sum to a target, where each candidate may be used an unlimited number of times.

How to think about it

Recognise the pattern

The signal is “find all combinations that meet a numeric constraint” — a sum, product, or count. Backtracking is the right fit because you’re enumerating candidates and have a clear pruning condition (partial sum already exceeded target). Unlike the subsets problem, here you have explicit pruning that cuts large branches early, making the search tractable even though candidates can repeat.

Build the approach step by step

Brute force generating every possible multiset from candidates and filtering by sum is exponential with no pruning — impractical.

Sorting + backtracking with early termination:

Sort the candidates first. Then in backtrack(start, path, remaining):

1. If remaining == 0 → found a valid combination, record it.
2. If remaining < 0 → overshot, return (prune).
3. Loop from start to end of candidates. For each c = candidates[i]:
   • If c > remaining, break immediately (sorted order means all later candidates are also too large).
   • Append c, recurse with start=i (same index = reuse allowed), then pop.

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

backtrack(start=0, path=[], rem=7)
  try 2 -> backtrack(0, [2], 5)
    try 2 -> backtrack(0, [2,2], 3)
      try 2 -> backtrack(0, [2,2,2], 1)
        try 2 -> rem=-1, prune
        try 3 -> rem=-2, prune
      try 3 -> backtrack(0, [2,2,3], 0)  FOUND [2,2,3]
    try 3 -> backtrack(1, [2,3], 2)
      try 3 -> rem=-1, prune
  try 3 -> backtrack(1, [3], 4)
    try 3 -> backtrack(1, [3,3], 1) -> prune all
  try 7 -> backtrack(3, [7], 0)  FOUND [7]

Complexity

• Time — O(n^(T/M)): approximately, where T is the target and M is the minimum candidate value. In the worst case (small candidates, large target) the tree is very deep.
• Space — O(T/M): maximum recursion depth is target divided by the smallest candidate. The output list is result-dependent.

Traps and variants