Combination Sum
Given distinct candidates and a target, return every unique combination that sums to target. The same number may be reused unlimited times.
Intuition
Build combinations by repeatedly choosing a candidate. To avoid duplicate combinations in a different order, only ever pick candidates from the current index onward — that fixes a non-decreasing order.
Backtracking is for building an answer piece by piece where each piece has several options and bad paths must be undone. The detail that separates the variants is what you pass as the next start: pass i to allow reusing the current element (unlimited supply), pass i + 1 to move on (each element once). Getting that one argument right is most of the difference between combination-sum I and II.
Approach
Blind enumeration explodes and duplicates
Generating every possible multiset of candidates and filtering those summing to the target is hopeless: the search space is huge, and it produces the same combination in many orders ([2,2,3], [2,3,2], [3,2,2]). Both problems are solved by structuring the search as a recursion that only ever extends combinations in one direction.
Recurse with a start index and a shrinking target
Backtracking explores choices one at a time. Pass a start index and a remaining target down the recursion. At each level you may pick candidates[i] for any i >= start, subtract it from remain, and recurse. The key to allowing reuse is recursing with the same index i (not i + 1), so the same number can be chosen repeatedly. Forcing choices to move forward from start is also what prevents reordered duplicates — combinations are always built in non-decreasing index order.
Base case, pruning, and undo
When remain hits exactly 0, we've found a valid combination — append a copy of the current path (not the live list, which keeps mutating). Prune any branch where a candidate exceeds remain, since it can't lead anywhere. After each recursive call, pop the last choice to backtrack and try the next — that undo is what lets one path object explore the whole tree. Roughly O(N^(target/min)) in the worst case.
Solution & live demo
Common pitfalls
Recursing with start instead of i
backtrack(start, remain - c, path)
backtrack(i, remain - c, path)
Passing start lets every level begin from the same place, so [2, 3] and [3, 2] both get generated — permutations of the same combination. Passing i pins each branch to non-decreasing order, which is exactly what makes a combination unordered.
Appending path instead of a copy
res.append(path)
res.append(path[:])
path is one list mutated in place for the whole search. Storing the reference means every stored answer aliases it, and once backtracking pops it empty, res is a list of empty lists. The snapshot must be taken at the moment of success.
Forgetting to pop after recursing
path.append(c) backtrack(i, remain - c, path)
path.append(c) backtrack(i, remain - c, path) path.pop()
Without the pop, the candidate stays in path while the loop tries the next branch, so choices from abandoned paths leak into unrelated ones. Every mutation before a recursive call needs its exact inverse after — that undo is the "backtrack".
Edge cases
The remain - c >= 0 guard skips it, so it never enters a combination.
Each distinct multiset is found once because choices only move forward from start.
Recursing with the same start index permits unlimited reuse, e.g. [2,2,3] for target 7.