Combination Sum II Visualizer & Step-by-Step Algorithm Solution

Find all unique combinations in candidates that sum to target. Each number may only be used once, using duplicate skipping and branch pruning.

Category: backtracking | Difficulty: Medium

Tags: Backtracking, Recursion, Array, Decision Tree, LeetCode 40

Combination Sum II

[]
0
Sorted Candidates Array
1
0
2
1
2
2
5
3
100%
state
target5
curr[]
currentSum0
solutionsFound0
Sort Candidates
1/49
Explanation

Sort candidates in ascending order: [1, 2, 2, 5]. Sorting allows skipping duplicate branches and enables early pruning.

Source Code
1function combinationSum2(candidates: number[], target: number): number[][] {
2 candidates.sort((a, b) => a - b);
3 const result: number[][] = [];
4 function backtrack(sum: number, curr: number[], start: number) {
5 if (sum === target) {
6 result.push([...curr]);
7 return;
8 }
9
10 if (sum > target) return;
11
12 for (let i = start; i < candidates.length; i++) {
13 if (i > start && candidates[i] === candidates[i - 1]) continue;
14 if (candidates[i] > target) break;
15 curr.push(candidates[i]);
16 backtrack(sum + candidates[i], curr, i + 1);
17 curr.pop();
18 }
19 }
20 backtrack(0, [], 0);
21 return result;
22}
03 — Reference
Sum