Bird
Raised Fist0
Interview Prepsubsets-combinationsmediumAmazonGoogle

Combination Sum II (No Reuse, Duplicates)

Choose your preparation mode4 modes available
Try ItSolutionTrace
▶
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.
📊
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.
Step 1/20
·Active fill★Answer cell
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/5)
1. Consider the following code snippet for counting max bitwise-OR subsets. What is the returned value when input is [1, 2, 3]? 
from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_or = 0
        count = 0
        for mask in range(1, 1 << n):
            current_or = 0
            for i in range(n):
                if mask & (1 << i):
                    current_or |= nums[i]
            if current_or > max_or:
                max_or = current_or
                count = 1
            elif current_or == max_or:
                count += 1
        return count

sol = Solution()
print(sol.countMaxOrSubsets([1, 2, 3]))
easy
A. 5
B. 4
C. 3
D. 6

Solution

  1. Step 1: Enumerate all non-empty subsets and their OR

    Subsets: {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} with ORs 1, 2, 3, 3, 3, 3, 3 respectively.

  2. Step 2: Identify max OR and count subsets with that OR

    Max OR is 3; subsets with OR=3 are {3}, {1,2}, {1,3}, {2,3}, {1,2,3} -> 5 subsets.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Counted 5 subsets with max OR 3 -> matches 5 [OK]
Hint: Count subsets with OR equal to max OR -> 5 [OK]
Common Mistakes:
  • Counting empty subset as valid
  • Miscounting subsets with max OR
2. What is the time complexity of the iterative lexicographic combinations generation algorithm for generating all combinations of size k from n elements?
medium
A. O(n^k) because each element can be chosen or not
B. O(k * (n choose k)) since each combination of size k is generated once and updated in O(k)
C. O(\u03C3(n choose k) * k) where \u03C3 is the number of combinations generated
D. O(n * k) because the outer loop runs n times and inner loop k times

Solution

  1. Step 1: Identify number of combinations

    There are exactly (n choose k) combinations to generate.

  2. Step 2: Analyze per-combination cost

    Each combination is generated and updated in O(k) time due to copying and resetting elements.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Time is proportional to number of combinations times combination size [OK]
Hint: Time depends on number of combinations times k [OK]
Common Mistakes:
  • Confusing with exponential O(n^k) or linear O(n*k) complexities
3. What is the time complexity of the space-optimized DP solution for counting subsets with sum K, given an array of size n and target sum K?
medium
A. O(2^n) because all subsets are explored
B. O(n * K) because the DP iterates over n elements and sums up to K
C. O(n + K) because it processes each element and sum once
D. O(n * K^2) because nested loops iterate over n and K twice

Solution

  1. Step 1: Identify loops in the DP

    Outer loop runs n times, inner loop runs up to K times for each element.

  2. Step 2: Calculate total operations

    Total operations = n * K, so time complexity is O(n * K).

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    DP iterates over all elements and sums up to K -> O(n * K) [OK]
Hint: DP complexity depends on n and K, not exponential [OK]
Common Mistakes:
  • Confusing DP with brute force exponential time
  • Assuming linear time due to single loops
4. Identify the bug in the following code snippet that generates subsets iteratively:
medium
A. Modifying subsets in place without copying causes all subsets to be identical
B. Extending result inside the loop causes infinite loop
C. Starting result with [[]] misses the empty subset
D. Using append instead of extend on subsets is incorrect

Solution

  1. Step 1: Analyze subset modification

    The code appends num directly to subsets in result, modifying them in place.

  2. Step 2: Consequence of in-place modification

    All subsets in result end up referencing the same list, causing duplicates and incorrect subsets.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Correct approach copies subsets before adding new elements [OK]
Hint: Always copy subsets before adding new elements [OK]
Common Mistakes:
  • Modifying lists in place
  • Extending result inside loop without fix
  • Wrong initial result value
5. Suppose the problem is modified so that letters can be toggled multiple times, allowing reuse of characters in permutations (e.g., toggling the same letter case multiple times in different positions). Which modification to the backtracking approach correctly handles this variant without generating duplicates?
hard
A. Use a visited set to track permutations and skip duplicates after generation
B. Modify recursion to allow toggling letters multiple times but prune branches that revisit the same index
C. Change the algorithm to generate permutations with replacement by increasing recursion depth beyond string length
D. Use iterative BFS with a queue that enqueues toggled strings and avoids revisiting states

Solution

  1. Step 1: Understand reuse variant

    Allowing reuse means letters can be toggled multiple times in different positions, increasing state space and possible duplicates.

  2. Step 2: Identify correct approach

    Iterative BFS with a queue can track states and avoid revisiting duplicates efficiently, unlike naive recursion which may generate duplicates or infinite loops.

  3. Step 3: Why other options fail

    Visited sets after generation are inefficient; pruning recursion by index doesn't prevent reuse; increasing recursion depth breaks problem constraints.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    BFS with state tracking handles reuse and duplicates [OK]
Hint: Use BFS with visited states to handle reuse [OK]
Common Mistakes:
  • Trying to prune recursion by index only
  • Ignoring duplicates generated by reuse
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard