04
Combination sum (Backtracking Sub-pattern)
Pick items that add up to a target. Sorting lets you stop the loop as soon as one item is too big.
Signals in the problem statement
- ›
"all unique combinations that sum to target"
- ›
"the same number may be chosen many times"
- ›
"each number may only be used once" with repeated values
What makes it different
Combination Sum allows reuse: recurse on the same index i. Combination Sum II forbids reuse and has duplicate values: recurse on i + 1 and skip equal neighbours at the same depth. Mixing up these two rules is the main bug in both.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Combination SumWalkthroughMediumBasic Anchor·LeetCode #39
- 2Combination Sum IIWalkthroughMediumBasic Reinforcement·LeetCode #40
Template
combination-sum-template.cpp
// Combination sum: target-driven. Sorted candidates let us stop as soon as one is too big.
// reuse allowed (LC 39): recurse on i no reuse (LC 40): recurse on i+1 and skip equal neighbours
void build(const vector<int>& c, int start, int remaining, bool reuse,
vector<int>& path, vector<vector<int>>& out) {
if (remaining == 0) { out.push_back(path); return; }
for (int i = start; i < (int)c.size(); i++) {
if (c[i] > remaining) break; // sorted: everything after is too big too
if (!reuse && i > start && c[i] == c[i - 1]) continue;
path.push_back(c[i]);
build(c, reuse ? i : i + 1, remaining - c[i], reuse, path, out);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int> candidates, int target, bool reuse) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> out;
vector<int> path;
build(candidates, 0, target, reuse, path, out);
return out;
}Remember this · Backtracking
Trigger
"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.
Think
At each step, what are my choices, and how do I undo a choice?
Key question
What is my state, when is it complete, and when do I prune?