DSA Tracker

Visualize

Combination Sum II

Sorted backtracking with a sibling-duplicate skip

time O(2^n)space O(n) recursion depth beyond the output

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.

Details

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].

Problem:Combination Sum IIMedium

Pattern:Backtracking with Constraints

Sorted backtracking with a sibling-duplicate skip

step 1 / 14

2
[0]
5
[1]
2
[2]
1
[3]
2
[4]

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

Every step in words

Show all 14 steps
  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.
  2. Sorted: [1, 2, 2, 2, 5]. Two things this buys: equal values sit side by side, so a duplicate sibling choice is just "same as the cell to my left", and once a candidate exceeds the remaining target every later one does too, so the loop can stop instead of scanning on.
  3. Take candidates[0]=1: path [1], remain 5 - 1 = 4. Recurse with start = 1, not 0: this cell is spent, so the deeper call may only look to its right.
  4. Take candidates[1]=2: path [1, 2], remain 4 - 2 = 2. Recurse with start = 2, not 1: this cell is spent, so the deeper call may only look to its right.
  5. Take candidates[2]=2: path becomes [1, 2, 2] and remain hits exactly 0, so a copy is recorded as answer #1. Each cell in the path is a different index, which is what "used once" means — two equal VALUES are fine when they are two different cells.
  6. candidates[3]=2 would only repeat the choice already made from the cell to its left, so it is skipped. Then candidates[4]=5 > remain=2. Because the list is sorted, nothing after it can fit either, so this loop BREAKs instead of testing the rest. Path [1, 2] is a dead end; back up one level.
  7. candidates[2]=2 and candidates[3]=2 would only repeat the choice already made from the cell to its left, so it is skipped. Then candidates[4]=5 > remain=4. Because the list is sorted, nothing after it can fit either, so this loop BREAKs instead of testing the rest. Path [1] is a dead end; back up one level.
  8. Take candidates[1]=2: path [2], remain 5 - 2 = 3. Recurse with start = 2, not 1: this cell is spent, so the deeper call may only look to its right.
  9. Take candidates[2]=2: path [2, 2], remain 3 - 2 = 1. Recurse with start = 3, not 2: this cell is spent, so the deeper call may only look to its right.
  10. candidates[3]=2 > remain=1. Because the list is sorted, nothing after it can fit either, so this loop BREAKs instead of testing the rest. Path [2, 2] is a dead end; back up one level.
  11. candidates[3]=2 would only repeat the choice already made from the cell to its left, so it is skipped. Then candidates[4]=5 > remain=3. Because the list is sorted, nothing after it can fit either, so this loop BREAKs instead of testing the rest. Path [2] is a dead end; back up one level.
  12. candidates[2]=2 and candidates[3]=2 equal the value just left of them and this call already branched on that value, so choosing them here would build the same combination again. Skip them (CONTINUE) and move on to candidates[4]=5.
  13. Take candidates[4]=5: path becomes [5] and remain hits exactly 0, so a copy is recorded as answer #2. Each cell in the path is a different index, which is what "used once" means — two equal VALUES are fine when they are two different cells.
  14. Search exhausted. 2 unique combinations sum to 5: [1, 2, 2], [5]. Without the sort-and-skip rule the same [1, 2, 2] would have surfaced once per interchangeable duplicate; the sorted break also pruned every branch the moment a candidate outgrew the remainder.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Combination Sum II in the editorAll Backtracking problemsBack to roadmap