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

This question probes two things at once: whether you can structure a backtracking search, and whether you control which index you recurse into — because that single number decides reuse, ordering, and whether you emit duplicate combinations. Brute-forcing every multiset and filtering by sum is exponential with no pruning, so the interviewer wants to see you prune and wants to see you manage the start index deliberately.

The shape is the standard backtracking trio: a choice, a recursion, an undo. Sort the candidates first so a break can kill a whole branch. Then backtrack(start, path, remaining) does three things. If remaining hits zero, you have a hit — record a copy of the path. Loop from start forward; the moment a candidate exceeds remaining, break, because the sorted order guarantees everything after it is too large as well. Otherwise append the candidate, recurse with start = i — passing i rather than i + 1 is what permits reusing the same value — then pop to undo and try the next. Sorting plus that start index together keep every combination unique and non-decreasing, so [2,2,3] appears once and [3,2,2] never does.

A worked example

def combination_sum(candidates, target):
    candidates.sort()                     # enables the break-on-overshoot
    result = []

    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(list(path))     # copy the path, not a reference
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining:
                break                     # sorted: every later candidate too big
            path.append(c)
            backtrack(i, path, remaining - c)   # i, NOT i+1: reuse allowed
            path.pop()                    # undo, try the next candidate

    backtrack(0, [], target)
    return result

print(combination_sum([2, 3, 6, 7], 7))
print(combination_sum([2, 3, 5], 8))
print(combination_sum([2], 1))

[[2, 2, 3], [7]]
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
[]

The first call shows reuse and uniqueness together: 2+2+3 reuses the 2 twice, 7 stands alone, and you never see the reordered [3,2,2]. The second confirms the search explores depth before width — 2+2+2+2 comes out before mixing in 3s, and each result is non-decreasing because the start index never lets a smaller value follow a larger one. The third, [2] against target 1, returns the empty list: the only candidate already overshoots, the break fires immediately, and nothing is recorded.