0
start idx
Find all unique combinations of candidates that sum to a target, where each candidate may be reused unlimited times. The key is a backtracking DFS that stays at the same index to allow reuse, and advances the start index at each loop iteration to prevent duplicate sets.
Given a list of distinct positive integers candidates and a target, return all unique combinations that sum to target. Each candidate may be used any number of times. Order within a combination doesn't matter, but no two combinations in the result may be the same multiset. candidates=[2,3,6,7], target=7 → [[2,2,3],[7]]. There are exactly two ways: three 2’s and a 3, or a single 7.
i (not i+1). To prevent generating the same multiset twice (e.g. both [2,3,2] and [2,2,3]), each recursive call only considers candidates at index start or later — you never go backwards. Sort first so you can prune entire branches early once a candidate exceeds the remaining target.[...path]) and return.start to end. The start parameter prevents going back to earlier candidates and thus avoids duplicate multisets.candidates[i] > remaining, break — no point continuing (sorted).candidates[i] onto path, then recurse with dfs(i, …) — same i, not i+1, so this candidate can be reused.i+1, exploring the branch that skips this candidate.i+1to the recursive call thinking “move forward so we don't repeat.” That prevents reuse — you'd never produce [2,2,3] at all. The correct rule: pass i to permit reuse; the outer loop handles the no-duplicates guarantee by never going backwards.Worst-case time is O(nt/m) where t is the target and m is the smallest candidate (maximum depth t/m, n branches at each level). Space is O(t/m) for the recursion stack plus output. Sorting is O(n log n) but dominates only for tiny inputs.
7.function combinationSum(candidates: number[], target: number): number[][] {
const result: number[][] = [];
const sorted = [...candidates].sort((a, b) => a - b);
function dfs(start: number, path: number[], remaining: number): void {
if (remaining === 0) {
result.push([...path]); // found a valid combination
return;
}
for (let i = start; i < sorted.length; i++) {
if (sorted[i] > remaining) break; // pruned: sorted, so all further also too large
path.push(sorted[i]);
dfs(i, path, remaining - sorted[i]); // i not i+1: allow reuse of same candidate
path.pop();
}
}
dfs(0, [], target);
return result;
}remaining reaches exactly 0, the path is a valid combination. We push a copy ([...path]) because path is mutated as the recursion unwinds.start, not 0, so we never pick a candidate that came before the current one in the sorted order. This guarantees no duplicate multisets. The break on line 11 exploits the sort: once sorted[i] > remaining, every subsequent candidate is even larger — safe to skip the entire tail.i (not i+1) is the reuse mechanism — the same candidate can appear multiple times. After the recursive call returns, path.pop() restores the path so the loop can explore the next candidate.if (i > start && candidates[i] === candidates[i-1]) continue and pass i+1 to the recursive call.dp[j] += dp[j - c].(path, start, remaining) tuples. Harder to read than the recursive version; only worth it if the interviewer asks.| "combinations that sum to target, reuse allowed" | backtracking DFS with start index i |
| "unique combinations / no duplicate sets" | pass start index, never go backwards |
| "prune when candidate > remaining" | sort + break (not continue) |
| "count combinations (not list)" | unbounded knapsack DP — O(n·target) |
function combinationSum(candidates: number[], target: number): number[][] {
const result: number[][] = [];
candidates.sort((a, b) => a - b);
function dfs(start: number, path: number[], remaining: number): void {
if (remaining === 0) { result.push([...path]); return; }
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break; // prune
path.push(candidates[i]);
dfs(i, path, remaining - candidates[i]); // reuse: i, not i+1
path.pop();
}
}
dfs(0, [], target);
return result;
}candidates=[2,3,6,7], target=7, what does the function return?if (sorted[i] > remaining) break; — why break and not continue?