Combination Sum: When Duplicates and Reuse Change Everything
The duplicate-skip pattern is what separates Combination Sum I from II. Master sort + skip, in-place grid marking for Word Search, and why `i > start` matters.
Combination Sum: When Duplicates and Reuse Change Everything
The basic backtracking template for subsets gets you far. Then you hit Combination Sum II and Word Search, and suddenly the same skeleton requires two very different tweaks. One problem has duplicates in the input that can't appear in duplicates in the output. The other takes backtracking into a 2D grid where the visited state is the board itself.
Both are medium-difficulty problems that feel hard until you understand exactly what changes and why.
Combination Sum I — Unlimited Reuse, Clean Input (LeetCode 39)
You have a list of distinct positive integers (candidates) and a target. Find all unique combinations where numbers sum to target. Each number can be used any number of times.
The key word is "unlimited reuse." In the subsets template, we passed i + 1 to prevent reusing the current element. Here, we pass i — same element stays eligible.
Brute force — enumerate every combination, prune on overshoot:
// Brute force: enumerate combinations with reuse, prune when the remainder goes negative
// Time: O(n^(t/m)) — t = target, m = smallest candidate. Reuse is unlimited, so the tree
// is NOT 2^n: its depth is bounded by t/m, not by n.
// Space: O(t/m) recursion depth
const combinationSum = (candidates, target) => {
const result = [];
const backtrack = (start, current, remaining) => {
if (remaining === 0) {
result.push([...current]);
return;
}
if (remaining < 0) return; // Overshot, prune
for (let i = start; i < candidates.length; i++) {
current.push(candidates[i]);
backtrack(i, current, remaining - candidates[i]); // i, not i+1 — allow reuse
current.pop();
}
};
backtrack(0, [], target);
return result;
};This is already the optimized version for this problem — there's no fundamentally better approach since you must enumerate all valid combinations. The pruning (remaining < 0) is the key optimization.
With sorting for better pruning:
// Sorted candidates allow early termination
// Time: O(n^(t/m)) where t = target, m = min candidate value
// Space: O(t/m) recursion depth
const combinationSum = (candidates, target) => {
candidates.sort((a, b) => a - b); // Sort ascending
const result = [];
const backtrack = (start, current, remaining) => {
if (remaining === 0) {
result.push([...current]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break; // Sorted: all subsequent also too big
current.push(candidates[i]);
backtrack(i, current, remaining - candidates[i]); // Reuse allowed
current.pop();
}
};
backtrack(0, [], target);
return result;
};Sorting lets you replace if (remaining < 0) return (check every iteration) with break (exit the loop entirely). When candidates[i] > remaining and the array is sorted, no later element can work either — prune the entire subtree.
Combination Sum II — Each Element Once, Duplicates in Input (LeetCode 40)
Same idea, but now:
- Each element can only be used once
- The input
candidatesmay contain duplicates - The output must contain only unique combinations
This is the trickier version. Using each element once is easy — change i to i + 1. The challenge is avoiding duplicate combinations when the input has repeated values.
Say candidates = [1, 1, 2] and target = 3. If you treat both 1s as distinct, you'd generate [1, 2] twice (once from each 1). The output should have it only once.
The fix: sort + skip duplicates at the same recursion level.
// Brute force — no dedup, generates duplicate combinations
// Time: O(2^n * n), Space: O(n)
const combinationSum2Brute = (candidates, target) => {
const result = [];
candidates.sort((a, b) => a - b);
const backtrack = (start, current, remaining) => {
if (remaining === 0) {
result.push([...current]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break;
current.push(candidates[i]);
backtrack(i + 1, current, remaining - candidates[i]); // i+1: no reuse
current.pop();
}
};
backtrack(0, [], target);
// Deduplicate via Set (expensive and ugly)
return [...new Set(result.map(JSON.stringify))].map(JSON.parse);
};Post-hoc deduplication via JSON.stringify works but is slow and gross. The clean solution skips duplicates at the recursion level:
// Optimal — sort + skip duplicate siblings
// Time: O(2^n) worst case, practically much faster with pruning
// Space: O(n) recursion depth
const combinationSum2 = (candidates, target) => {
candidates.sort((a, b) => a - b);
const result = [];
const backtrack = (start, current, remaining) => {
if (remaining === 0) {
result.push([...current]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break;
// Skip duplicate values at the same recursion depth
// i > start ensures we don't skip the first occurrence
if (i > start && candidates[i] === candidates[i - 1]) continue;
current.push(candidates[i]);
backtrack(i + 1, current, remaining - candidates[i]);
current.pop();
}
};
backtrack(0, [], target);
return result;
};i > start && candidates[i] === candidates[i - 1]. The i > start part is critical — it allows using the first occurrence of a duplicate value, but skips subsequent identical values at the same level of the recursion tree. Without i > start, you'd skip the first occurrence too and miss valid combinations.Here's the visual intuition for candidates = [1, 1, 2], target = 3:
At the root level (start = 0), when we encounter the second 1 at index 1, we skip it (i > start is true since 1 > 0, and candidates[1] === candidates[0]). We only use the first 1 from the root. But at the next level (start = 1), the second 1 at index 1 is the first element we see, so i > start is false (1 > 1 is false) and we use it. That's how both 1s get used in the combination [1, 1, 2] — just not as two separate starting choices from the same level.
Word Search — Backtracking in a 2D Grid (LeetCode 79)
Given a 2D grid of characters and a word, return true if the word exists in the grid formed by adjacent (horizontally/vertically) cells where each cell is used at most once.
This is backtracking on a grid. Instead of an array of choices, you have four directional neighbors. Instead of a used[] array, you mark cells in the board itself.
// Brute force — check every cell as potential start, no visited tracking
// Would reuse cells, so this is incorrect but shows the structure
const exist = (board, word) => {
const rows = board.length;
const cols = board[0].length;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(board, r, c, 0, word)) return true;
}
}
return false;
function dfs(board, r, c, idx, word) {
if (idx === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
if (board[r][c] !== word[idx]) return false;
// Missing: visited tracking — this version would reuse cells
return dfs(board, r+1, c, idx+1, word) ||
dfs(board, r-1, c, idx+1, word) ||
dfs(board, r, c+1, idx+1, word) ||
dfs(board, r, c-1, idx+1, word);
}
};Correct solution — mark and unmark visited cells in-place:
// Grid backtracking with in-place visited marking
// Time: O(rows * cols * 4^L) where L = word length (each cell branches to 4 neighbors)
// Space: O(L) recursion depth (no extra visited array — board used in-place)
const exist = (board, word) => {
const rows = board.length;
const cols = board[0].length;
const dfs = (r, c, idx) => {
if (idx === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
if (board[r][c] !== word[idx]) return false;
const temp = board[r][c];
board[r][c] = '#'; // Mark as visited (in-place)
const found = dfs(r + 1, c, idx + 1) ||
dfs(r - 1, c, idx + 1) ||
dfs(r, c + 1, idx + 1) ||
dfs(r, c - 1, idx + 1);
board[r][c] = temp; // Unmark (backtrack)
return found;
};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
};The board[r][c] = '#' trick is the backtracking undo in disguise. You temporarily corrupt the cell to prevent revisiting it, then restore it after the recursive calls return. No extra visited[][] array needed — the board is its own visited state.
board[r][c] = '#' then restore) avoids an extra O(rows * cols) visited array. Just make sure the sentinel value ('#') can't appear in the board's valid characters. For Word Search, any character not in the alphabet works.One quick optimization: if the word needs more copies of some character than the board contains, no search can succeed, so bail out before recursing.
// Early exit: compare character frequencies board vs word
const canPossiblyExist = (board, word) => {
const have = new Map();
for (const ch of board.flat()) have.set(ch, (have.get(ch) ?? 0) + 1);
const need = new Map();
for (const ch of word) need.set(ch, (need.get(ch) ?? 0) + 1);
for (const [ch, count] of need) {
if ((have.get(ch) ?? 0) < count) return false;
}
return true;
};Note that word is a string, so it has no .filter — iterate it with for...of or spread it into an array first.
Patterns to Lock In
The duplicate-skip pattern appears in multiple problems:
// This exact pattern handles duplicates in sorted arrays
if (i > start && candidates[i] === candidates[i - 1]) continue;You'll see this in:
- Combination Sum II (this problem)
- Subsets II (LeetCode 90)
- Permutations II (LeetCode 47, with
used[]instead ofstart)
In Permutations II, the duplicate-skip is slightly different because you're not using start:
// Permutations II variant (with used[] tracking)
if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;The !used[i - 1] condition ensures that when the previous duplicate wasn't used in this branch (already backtracked past it), we skip the current duplicate to avoid regenerating the same permutation.
Interview Tips
Sort the input first. For any backtracking problem with duplicates, sorting is step zero. It clusters duplicates together, enabling the candidates[i] === candidates[i - 1] check, and allows early break when candidates exceed the target.
Distinguish "no reuse" from "no duplicate outputs." These are different constraints. No reuse: pass i + 1. No duplicate outputs with duplicate inputs: sort + skip at the same level. You can need both at once (Combination Sum II), or just one (Combination Sum I, Subsets II).
For grid problems, ask if diagonal moves are allowed (they're not in Word Search). Always clarify the grid bounds and available moves before coding. The in-place marking trick is clean enough to use in interviews without apology — just mention that you're restoring the original value.
Time complexity for Combination Sum is hard to express cleanly. In interviews, O(n^(t/m)) is the standard answer where t = target and m = minimum candidate value — that's the depth of the tree times the branching factor at each level. Don't sweat the exact derivation; just explain "each branch reduces the remaining sum by at least the minimum element, so the depth is bounded by target/min."
Comments (0)
No comments yet. Be the first to share your thoughts!
Related Articles
