Pattern visualizer

Combination Sum II

Combination Sum let a value be reused, so the recursive call stayed at the same index. Here every cell is spent once, so the call advances to i + 1 — and that alone is not enough, because the input has repeated values. Picking the first 2 and then the second 2 in a sibling loop branch builds the same multiset twice. Sorting makes equal values neighbours, so the rule is one comparison: inside a single loop, skip a candidate that equals the one before it (i > start), since that value has already been branched on at this level. Taking a duplicate in a DEEPER call is still allowed, which is how [1, 2, 2] is found. Sorting also lets the loop break the moment a candidate exceeds the remaining target. Animated on: candidates = [2, 5, 2, 1, 2], target = 5. Each cell may be used once per combination and the answer must contain no duplicate combinations. Answer: [1, 2, 2], [5]..

Sorted backtracking with a sibling-duplicate skip

time O(2^n)space O(n) recursion depth beyond the outputstep 1 / 14

[0]

[1]

[2]

[3]

[4]

line 1

candidates = [2, 5, 2, 1, 2], target = 5. Duplicates are scattered, so a search cannot tell "the second 2" from "the first 2" and would report [1, 2, 2] three separate times. Sorting is the fix: equal values become neighbours, and the rule becomes local.

Pseudocode

1SORT candidates
2FUNCTION backtrack(start, remain, path)
3  IF remain = 0
4    APPEND COPY(path) TO out
5    RETURN
6  FOR i <- start TO LENGTH(candidates) - 1
7    IF i > start AND candidates[i] = candidates[i - 1]
8      CONTINUE
9    IF candidates[i] > remain
10      BREAK
11    APPEND candidates[i] TO path
12    backtrack(i + 1, remain - candidates[i], path)
13    REMOVE LAST FROM path
14backtrack(0, target, EMPTY LIST)

← / → step · space play · Home restart

Where to practice Backtracking

Practice Backtracking problems All Backtracking problems Back to roadmap