Combination Sum II (No Reuse, Duplicates)

▶

Steps

setup

Sort candidates and start recursion

Candidates are sorted to [1,1,2,5,6,7,10] to group duplicates and enable pruning. The initial call to backtrack starts at index 0 with an empty path and target 8.

💡 Sorting is crucial to handle duplicates and prune early, setting the stage for efficient backtracking.

Line:

candidates.sort()
backtrack(0, [], target)

💡 Sorting groups duplicates and allows pruning when candidates exceed the target.

traverse

Choose candidate 1 at index 0

At index 0, candidate 1 is chosen because it does not exceed the target 8. The algorithm recurses with start=1, path=[1], and target=7.

💡 Choosing the first candidate explores combinations starting with 1, the smallest number.

Line:

prev = -1
for i in range(start, len(candidates)):
  if candidates[i] > target: break
  if candidates[i] == prev: continue
  prev = candidates[i]
  backtrack(i + 1, path + [candidates[i]], target - candidates[i])

💡 The recursion explores including the first candidate and reduces the target accordingly.

traverse

Choose candidate 1 at index 1 (duplicate allowed here)

At index 1, candidate 1 is chosen again because it is not a duplicate at this recursion level (prev = -1). The algorithm recurses with start=2, path=[1,1], target=6.

💡 Duplicates are allowed if they come from different recursion levels, enabling combinations like [1,1,...].

Line:

prev = -1
for i in range(start, len(candidates)):
  if candidates[i] > target: break
  if candidates[i] == prev: continue
  prev = candidates[i]
  backtrack(i + 1, path + [candidates[i]], target - candidates[i])

💡 The algorithm explores deeper with two 1's in the path, reducing target to 6.

traverse

Choose candidate 2 at index 2

At index 2, candidate 2 is chosen because 2 <= target 6. The algorithm recurses with start=3, path=[1,1,2], target=4.

💡 Choosing 2 extends the combination, reducing the target further.

Line:

prev = -1
for i in range(start, len(candidates)):
  if candidates[i] > target: break
  if candidates[i] == prev: continue
  prev = candidates[i]
  backtrack(i + 1, path + [candidates[i]], target - candidates[i])

💡 The path grows to [1,1,2], target shrinks to 4.

traverse

Choose candidate 5 at index 3

At index 3, candidate 5 is greater than target 4, so the loop breaks to prune this path.

💡 Pruning stops exploration early when candidates exceed the target, saving time.

Line:

if candidates[i] > target:
  break

💡 No further candidates at this level can fit, so backtrack occurs.

traverse

Backtrack and choose candidate 5 at index 3 from path [1,1]

Backtracking to index 2 level, candidate 5 at index 3 is chosen since 5 <= target 6. Recurse with start=4, path=[1,1,5], target=1.

💡 Backtracking allows exploring alternative candidates after pruning or finishing a path.

Line:

prev = -1
for i in range(start, len(candidates)):
  if candidates[i] > target: break
  if candidates[i] == prev: continue
  prev = candidates[i]
  backtrack(i + 1, path + [candidates[i]], target - candidates[i])

💡 The path changes to [1,1,5], target reduces to 1.

prune

Candidate 6 at index 4 exceeds target 1, prune

At index 4, candidate 6 is greater than target 1, so the loop breaks and this path is pruned.

💡 Pruning prevents unnecessary exploration when candidates are too large.

Line:

if candidates[i] > target:
  break

💡 No valid combinations can be formed beyond this point on this path.

traverse

Backtrack to path [1] and choose candidate 2 at index 2

Backtracking to index 1 level, candidate 2 at index 2 is chosen since 2 <= target 7. Recurse with start=3, path=[1,2], target=5.

💡 Backtracking explores new branches by choosing different candidates at previous recursion levels.

Line:

prev = -1
for i in range(start, len(candidates)):
  if candidates[i] > target: break
  if candidates[i] == prev: continue
  prev = candidates[i]
  backtrack(i + 1, path + [candidates[i]], target - candidates[i])

💡 The path updates to [1,2], target reduces to 5.

traverse

Choose candidate 5 at index 3

At index 3, candidate 5 is chosen because 5 <= target 5. Recurse with start=4, path=[1,2,5], target=0.

💡 Choosing candidate 5 completes a valid combination since target reaches zero.

Line:

backtrack(i + 1, path + [candidates[i]], target - candidates[i])

💡 The path [1,2,5] sums exactly to the original target 8.

insert

Add valid combination [1,2,5] to answers and backtrack

Since target is zero, the current path [1,2,5] is a valid combination and is added to the results. The function returns to explore other candidates.

💡 Finding a target zero means a complete valid combination is found.

Line:

if target == 0:
  res.append(path[:])
  return

💡 Valid combinations are collected when the target reaches zero.

prune

Backtrack and prune candidate 6 at index 4

Backtracking to index 3 level, the next candidate 6 at index 4 is checked. Since 6 > target 5, pruning occurs and the loop breaks.

💡 Pruning avoids exploring candidates that cannot fit the remaining target.

Line:

if candidates[i] > target:
  break

💡 No further candidates at this level can form valid combinations.

traverse

Backtrack to path [1] and choose candidate 5 at index 3

Backtracking to index 1 level, candidate 5 at index 3 is chosen since 5 <= target 7. Recurse with start=4, path=[1,5], target=2.

💡 Backtracking explores new branches by choosing different candidates at previous recursion levels.

Line:

prev = -1
for i in range(start, len(candidates)):
  if candidates[i] > target: break
  if candidates[i] == prev: continue
  prev = candidates[i]
  backtrack(i + 1, path + [candidates[i]], target - candidates[i])

💡 The path updates to [1,5], target reduces to 2.

prune

Candidate 6 at index 4 exceeds target 2, prune

At index 4, candidate 6 is greater than target 2, so the loop breaks and this path is pruned.

💡 Pruning prevents unnecessary exploration when candidates are too large.

Line:

if candidates[i] > target:
  break

💡 No valid combinations can be formed beyond this point on this path.

traverse

Backtrack to path [] and skip duplicate candidate 1 at index 1

Backtracking to root level, candidate 1 at index 1 is skipped because it is a duplicate of candidate 1 at index 0 at the same recursion level.

💡 Skipping duplicates at the same recursion level avoids repeated combinations.

Line:

if candidates[i] == prev:
  continue

💡 Duplicate candidates at the same level are not explored again.

traverse

Choose candidate 2 at index 2 from root

At root level, candidate 2 at index 2 is chosen since 2 <= target 8. Recurse with start=3, path=[2], target=6.

💡 Choosing candidate 2 explores combinations starting with 2.

Line:

prev = -1
for i in range(start, len(candidates)):
  if candidates[i] > target: break
  if candidates[i] == prev: continue
  prev = candidates[i]
  backtrack(i + 1, path + [candidates[i]], target - candidates[i])

💡 The path updates to [2], target reduces to 6.

traverse

Choose candidate 6 at index 4

At index 4, candidate 6 is chosen because 6 <= target 6. Recurse with start=5, path=[2,6], target=0.

💡 Choosing candidate 6 completes a valid combination since target reaches zero.

Line:

backtrack(i + 1, path + [candidates[i]], target - candidates[i])

💡 The path [2,6] sums exactly to the original target 8.

insert

Add valid combination [2,6] to answers and backtrack

Since target is zero, the current path [2,6] is a valid combination and is added to the results. The function returns to explore other candidates.

💡 Finding a target zero means a complete valid combination is found.

Line:

if target == 0:
  res.append(path[:])
  return

💡 Valid combinations are collected when the target reaches zero.

traverse

Backtrack to path [] and choose candidate 5 at index 6

Backtracking to root level, candidate 5 at index 6 is chosen since 5 <= target 8. Recurse with start=7, path=[5], target=3.

💡 Backtracking explores new branches by choosing different candidates at root level.

Line:

prev = -1
for i in range(start, len(candidates)):
  if candidates[i] > target: break
  if candidates[i] == prev: continue
  prev = candidates[i]
  backtrack(i + 1, path + [candidates[i]], target - candidates[i])

💡 The path updates to [5], target reduces to 3.

backtrack

No candidates left to choose, backtrack

At index 7, no candidates remain, so the algorithm backtracks to explore other branches.

💡 Backtracking occurs when no further candidates are available.

Line:

for i in range(start, len(candidates)):
  ...

💡 The recursion unwinds to previous levels to try other options.

reconstruct

Backtrack complete, final answers collected

All recursion calls have returned. The collected answers are [[1,1,6],[1,2,5],[1,7],[2,6]].

💡 The final result contains all unique combinations summing to the target.

Line:

return res

💡 Backtracking with sorting and duplicate skipping finds all unique valid combinations.

from typing import List

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()  # STEP 1
    res = []
    def backtrack(start, path, target):
        if target == 0:  # STEP 10,17
            res.append(path[:])
            return
        prev = -1
        for i in range(start, len(candidates)):  # STEP 2-19
            if candidates[i] > target:  # STEP 5,7,13
                break
            if candidates[i] == prev:  # STEP 14
                continue
            prev = candidates[i]
            backtrack(i + 1, path + [candidates[i]], target - candidates[i])
    backtrack(0, [], target)  # STEP 1
    return res  # STEP 20

if __name__ == '__main__':
    print(combinationSum2([10,1,2,7,6,1,5], 8))

📊

Combination Sum II (No Reuse, Duplicates) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step recursion tree helps you understand how backtracking explores all unique combinations without repetition or duplicates, which is hard to grasp from code alone.

enteringstart=0path=[]target=8

Call Path (current → root)

backtrack(0, [], 8)

Remaining

i=0 to 6

enteringstart=1path=[1]target=7

Call Path (current → root)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Remaining

i=1 to 6

Partial: [1]

enteringstart=2path=[1,1]target=6

Call Path (current → root)

backtrack(2, [1,1], 6)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Remaining

i=2 to 6

Partial: [1, 1]

enteringstart=3path=[1,1,2]target=4

Call Path (current → root)

backtrack(3, [1,1,2], 4)

backtrack(2, [1,1], 6)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Remaining

i=3 to 6

Partial: [1, 1, 2]

pruningstart=3path=[1,1,2]target=4

Call Path (current → root)

backtrack(3, [1,1,2], 4)

backtrack(2, [1,1], 6)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Tried

3

Partial: [1, 1, 2]

✂ candidate 5 > target 4

enteringstart=4path=[1,1,5]target=1

Call Path (current → root)

backtrack(4, [1,1,5], 1)

backtrack(2, [1,1], 6)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Remaining

i=4 to 6

Partial: [1, 1, 5]

pruningstart=4path=[1,1,5]target=1

Call Path (current → root)

backtrack(4, [1,1,5], 1)

backtrack(2, [1,1], 6)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Tried

4

Partial: [1, 1, 5]

✂ candidate 6 > target 1

enteringstart=3path=[1,2]target=5

Call Path (current → root)

backtrack(3, [1,2], 5)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Remaining

i=3 to 6

Partial: [1, 2]

enteringstart=4path=[1,2,5]target=0

Call Path (current → root)

backtrack(4, [1,2,5], 0)

backtrack(3, [1,2], 5)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Partial: [1, 2, 5]

backtrackingstart=4path=[1,2,5]target=0

Call Path (current → root)

backtrack(4, [1,2,5], 0)

backtrack(3, [1,2], 5)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Partial: [1, 2, 5]

Found 1: [1,2,5]

pruningstart=3path=[1,2]target=5

Call Path (current → root)

backtrack(3, [1,2], 5)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Tried

3

Partial: [1, 2]

✂ candidate 6 > target 5

Found 1: [1,2,5]

enteringstart=4path=[1,5]target=2

Call Path (current → root)

backtrack(4, [1,5], 2)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Remaining

i=4 to 6

Partial: [1, 5]

Found 1: [1,2,5]

pruningstart=4path=[1,5]target=2

Call Path (current → root)

backtrack(4, [1,5], 2)

backtrack(1, [1], 7)

backtrack(0, [], 8)

Tried

4

Partial: [1, 5]

✂ candidate 6 > target 2

Found 1: [1,2,5]

choosingstart=0path=[]target=8

Call Path (current → root)

backtrack(0, [], 8)

Tried

0

Remaining

123456

Found 1: [1,2,5]

enteringstart=3path=[2]target=6

Call Path (current → root)

backtrack(3, [2], 6)

backtrack(0, [], 8)

Remaining

i=3 to 6

Partial: [2]

Found 1: [1,2,5]

enteringstart=5path=[2,6]target=0

Call Path (current → root)

backtrack(5, [2,6], 0)

backtrack(3, [2], 6)

backtrack(0, [], 8)

Partial: [2, 6]

Found 1: [1,2,5]

backtrackingstart=5path=[2,6]target=0

Call Path (current → root)

backtrack(5, [2,6], 0)

backtrack(3, [2], 6)

backtrack(0, [], 8)

Partial: [2, 6]

Found 2: [1,2,5] [2,6]

enteringstart=7path=[5]target=3

Call Path (current → root)

backtrack(6, [5], 3)

backtrack(0, [], 8)

Partial: [5]

Found 2: [1,2,5] [2,6]

backtrackingstart=7path=[5]target=3

Call Path (current → root)

backtrack(6, [5], 3)

backtrack(0, [], 8)

Partial: [5]

Found 2: [1,2,5] [2,6]

Answer: [[1,1,6],[1,2,5],[1,7],[2,6]]

Total calls: 20 · Pruned: 5

Key Takeaways

✓ Sorting candidates is essential to efficiently skip duplicates and prune the search space.

Without sorting, duplicate skipping and pruning would be much harder to implement and visualize.

✓ Backtracking explores all unique combinations by including or skipping candidates, with pruning to avoid unnecessary work.

Seeing the recursion tree shows how the algorithm branches and prunes, which is not obvious from code alone.

✓ Skipping duplicates at the same recursion level prevents repeated combinations, ensuring uniqueness in the results.

The trace shows exactly when and why duplicates are skipped, clarifying this subtle but critical step.

Practice

1. You are given an array of positive integers and a number k. The task is to determine if the array can be partitioned into k subsets such that the sum of elements in each subset is equal. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming based on subset sums without pruning or memoization

B. Greedy algorithm that picks the largest elements first and assigns them to subsets

C. Backtracking with bitmask memoization to explore subsets and prune invalid states

D. Sorting and then using a sliding window to find equal sum partitions

Solution

1. Step 1: Understand problem constraints and complexity

   The problem requires partitioning into exactly k subsets with equal sums, which is NP-complete and requires exploring combinations exhaustively.

2. Step 2: Evaluate algorithm suitability

   Greedy and sliding window approaches fail to guarantee correctness because they don't explore all combinations. Simple DP without pruning is inefficient and incomplete. Backtracking with bitmask memoization efficiently prunes and caches states, guaranteeing optimality.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backtracking with memoization handles all subsets optimally [OK]

Hint: Bitmask memoization prunes repeated subset states [OK]

Common Mistakes:

• Assuming greedy always works for equal sum partition
• Confusing subset sum DP with partitioning into k subsets

2. What is the worst-case time complexity of the optimal backtracking solution with sum bound pruning for Combination Sum III (k numbers from 1 to 9 summing to n)?

medium

A. O(k!) because permutations of k numbers are explored

B. O(k * n) because we explore all sums up to n for k elements

C. O(n^k) because we try all sequences of length k with sum n

D. O(2^9) because each number 1-9 can be either included or excluded, pruning reduces calls but worst case remains exponential

Solution

1. Step 1: Identify search space size

   Numbers 1 to 9 can be included or excluded, so 2^9 subsets possible.

2. Step 2: Consider pruning effect

   Pruning reduces calls but worst-case complexity remains O(2^9) since all subsets might be explored.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking worst case is exponential in number of candidates [OK]

Hint: Backtracking subsets of 9 elements is O(2^9) worst case [OK]

Common Mistakes:

• Confusing with DP complexity O(k*n)
• Thinking permutations cause factorial complexity

3. The following code attempts to solve the Matchsticks to Square problem using backtracking with bitmask and memoization. Identify the line containing the subtle bug that can cause incorrect results or infinite recursion.

medium

A. Line with 'if total % 4 != 0: return false' (no divisibility check)

B. Line with 'matchsticks.sort(reverse=true)' (missing sorting causes inefficiency)

C. Line with 'memo[(used_mask, curr_sum, sides_formed)] = false' (incorrect memoization)

D. Line with recursive call 'backtrack(next_mask, next_sum, sides_formed)' missing return statement

Solution

1. Step 1: Identify missing return in recursion

   The recursive call without return means the function ignores successful paths, causing incorrect results or infinite recursion.

2. Step 2: Confirm other lines are correct

   Divisibility check is present, sorting is done, and memoization line is correct for caching failures.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing return in recursive call breaks backtracking correctness [OK]

Hint: Missing return in recursive call breaks correctness [OK]

Common Mistakes:

• Forgetting to return recursive call result
• Skipping divisibility check
• Not sorting before backtracking

4. Examine the following buggy code snippet from the trie-based solution. Which line contains the subtle bug that causes incorrect counts for some puzzles?

medium

A. Line where node.count is incremented

B. Line missing filtering words with more than 7 unique letters before insertion

C. Line checking if bit is set in mask during insertion

D. Line checking if puzzle_mask contains child bit during dfs

Solution

1. Step 1: Identify filtering step

   The code inserts all words regardless of unique letter count, causing large trie and slow traversal.

2. Step 2: Understand impact

   Words with >7 unique letters cannot match puzzles (7 letters max), so filtering them out is necessary for correctness and efficiency.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Filtering missing leads to incorrect counts and performance issues [OK]

Hint: Filter words with >7 unique letters before insertion [OK]

Common Mistakes:

• Not filtering large words
• Incorrect bit checks
• Misplaced count increments

5. Suppose you want to generate all combinations of size k from numbers 1 to n, but now elements can be reused multiple times in a combination (combinations with replacement). Which modification to the backtracking approach correctly handles this?

hard

A. Use iterative lexicographic generation without any changes

B. Change the recursive call to backtrack(i + 1, path) to prevent reuse of elements

C. Change the recursive call to backtrack(i, path) to allow reuse of the current element

D. Sort the input array before backtracking to handle duplicates

Solution

1. Step 1: Understand combinations with replacement allow repeated elements

   To allow reuse, the recursive call must not increment start index beyond current element.

2. Step 2: Modify recursion to backtrack(i, path) to allow current element reuse

   This ensures the same element can be chosen multiple times in subsequent recursive calls.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Using backtrack(i, path) enables combinations with replacement [OK]

Hint: Reuse requires recursive calls with same start index [OK]

Common Mistakes:

• Incrementing start index prevents element reuse