Permutations II (With Duplicates)

▶

Steps

setup

Initialize and Sort Input

The input array [1,1,2] is sorted to group duplicates together, resulting in [1,1,2]. This sorting is essential for the skip condition to work correctly.

💡 Sorting groups duplicates so the algorithm can easily detect and skip repeated elements at each recursion level.

Line:

nums.sort()

💡 Sorting is a prerequisite that enables efficient duplicate skipping during backtracking.

fill_row

Start Backtracking at start=0, Initialize Seen Set and Choose i=0

At recursion level start=0, initialize an empty set 'seen' to track which elements have been fixed at this position to avoid duplicates. Choose index i=0 to fix at position start=0. Since 1 is not in 'seen', add it and swap nums[0] with nums[0] (no change).

💡 The 'seen' set prevents fixing the same element multiple times at the current recursion level, which would generate duplicate permutations. Fixing an element at the current position and recursing explores permutations starting with that element.

Line:

seen = set()
if nums[i] not in seen:
    seen.add(nums[i])
    nums[start], nums[i] = nums[i], nums[start]

💡 Tracking fixed elements at each recursion level is key to pruning duplicate branches. The first unique element at this level is fixed to start the permutation branch.

traverse

Recurse to start=1 and Initialize Seen Set

After fixing nums[0]=1, recurse to backtrack(start=1) to fix the next position. At recursion level start=1, initialize an empty set 'seen' to track fixed elements at this position.

💡 Recursion explores deeper positions to build the permutation step by step. Each recursion level has its own 'seen' set to avoid duplicates locally.

Line:

backtrack(start + 1)
seen = set()

💡 The recursion depth increases to fix the next element in the permutation. Local duplicate tracking is reset at each recursion depth.

fill_cells

Choose i=1 at start=1, Fix nums[1]=1 and Recurse to start=2

Choose index i=1 to fix at position start=1. Since nums[1]=1 is not in 'seen', add it and swap nums[1] with nums[1] (no change). Then recurse to backtrack(start=2) to fix the last position.

💡 Fixing the second 1 at position 1 continues building the permutation branch. Recursion continues until all positions are fixed to form a complete permutation.

Line:

if nums[i] not in seen:
    seen.add(nums[i])
    nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)

💡 Duplicates at this level are tracked to avoid repeated permutations. The recursion depth increases to complete the permutation.

fill_cells

Initialize Seen Set at start=2 and Choose i=2, Fix nums[2]=2

At recursion level start=2, initialize an empty set 'seen' to track fixed elements. Choose index i=2 to fix at position start=2. Since nums[2]=2 is not in 'seen', add it and swap nums[2] with nums[2] (no change).

💡 Each recursion level independently tracks duplicates to prune redundant branches. Fixing the last element completes the current permutation branch.

Line:

seen = set()
if nums[i] not in seen:
    seen.add(nums[i])
    nums[start], nums[i] = nums[i], nums[start]

💡 Duplicate tracking resets at each recursion depth. The last element is fixed to complete the permutation.

reconstruct

Add Complete Permutation [1,1,2] to Results and Backtrack to start=2

Since start equals the length of nums, the current permutation [1,1,2] is complete and added to the results list. Then backtrack by swapping nums[2] and nums[2] back to restore the array to [1,1,2] before exploring other choices at start=2.

💡 Leaf nodes represent complete permutations that are collected as answers. Backtracking restores state to explore alternative branches.

Line:

if start == len(nums):
    res.append(nums[:])
    return
nums[start], nums[i] = nums[i], nums[start]

💡 Completed permutations are recorded for final output. Backtracking is essential to explore all unique permutations.

delete

Backtrack to start=1, Undo Swap and Choose i=2, Fix nums[2]=2

Backtrack by swapping nums[1] and nums[1] back to restore the array to [1,1,2]. Then choose index i=2 to fix at position start=1. Since nums[2]=2 is not in 'seen', add it and swap nums[1] and nums[2], resulting in [1,2,1].

💡 Backtracking restores the array to try other elements at this recursion level. Swapping places the new element at the current position to explore new permutations.

Line:

nums[start], nums[i] = nums[i], nums[start]
if nums[i] not in seen:
    seen.add(nums[i])
    nums[start], nums[i] = nums[i], nums[start]

💡 Backtracking at each recursion level enables full exploration of permutations. Swapping enables exploring permutations with different elements fixed at the current position.

traverse

Recurse to start=2 with nums=[1,2,1], Initialize Seen Set and Choose i=2

Recurse to backtrack(start=2) to fix the last position with the updated array [1,2,1]. Initialize an empty 'seen' set at start=2 to track duplicates. Choose index i=2 to fix at position start=2. Since nums[2]=1 is not in 'seen', add it and swap nums[2] with nums[2] (no change).

💡 Recursion continues to complete the permutation with the new partial state. Duplicate tracking resets at each recursion level regardless of array state. Fixing the last element completes this permutation branch.

Line:

backtrack(start + 1)
seen = set()
if nums[i] not in seen:
    seen.add(nums[i])
    nums[start], nums[i] = nums[i], nums[start]

💡 Recursion depth increases to finalize the permutation. Duplicate skipping is local to recursion depth and array state. Completing the permutation with the new prefix.

reconstruct

Add Complete Permutation [1,2,1] to Results and Backtrack to start=2

Since start equals the length of nums, add the complete permutation [1,2,1] to the results list. Backtrack by swapping nums[2] and nums[2] back to restore the array to [1,2,1].

💡 Leaf node reached; collect the new unique permutation. Restore state to explore other choices at start=2.

Line:

if start == len(nums):
    res.append(nums[:])
    return
nums[start], nums[i] = nums[i], nums[start]

💡 New unique permutation found and recorded. Backtracking enables exploring all branches.

delete

Backtrack to start=1, Undo Swap and Backtrack to start=0, Skip Duplicate i=1

Backtrack by swapping nums[1] and nums[1] back to restore the array to [1,1,2]. At start=0, attempt to choose i=1 (nums[1]=1), but since 1 is already in 'seen', skip this choice to avoid duplicate permutations.

💡 Backtracking restores the array to try other elements at this recursion level. Skipping duplicates at the same recursion level prevents redundant branches.

Line:

nums[start], nums[i] = nums[i], nums[start]
if nums[i] in seen:
    continue

💡 Backtracking at each recursion level enables full exploration of permutations. Duplicate skipping prunes the recursion tree efficiently.

fill_cells

Choose i=2 at start=0, Fix nums[2]=2 and Recurse to start=1

Choose index i=2 to fix at position start=0. Since nums[2]=2 is not in 'seen', add it and swap nums[0] and nums[2], resulting in [2,1,1]. Recurse to backtrack(start=1) to fix the next position.

💡 Fixing a new unique element at the first position explores permutations starting with 2. Recursion continues to build permutations starting with 2.

Line:

if nums[i] not in seen:
    seen.add(nums[i])
    nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)

💡 Swapping enables exploring permutations with different first elements. Recursion depth increases to fix the second element.

fill_cells

Initialize Seen Set at start=1 and Choose i=1, Fix nums[1]=1

Initialize an empty 'seen' set at start=1 to track duplicates for the second position. Choose index i=1 to fix at position start=1. Since nums[1]=1 is not in 'seen', add it and swap nums[1] with nums[1] (no change).

💡 Duplicate tracking resets at each recursion level. Fixing the first 1 at second position continues building the permutation.

Line:

seen = set()
if nums[i] not in seen:
    seen.add(nums[i])
    nums[start], nums[i] = nums[i], nums[start]

💡 Duplicate skipping is local to recursion depth. Duplicates tracked to avoid repeated permutations.

traverse

Recurse to start=2 with nums=[2,1,1], Initialize Seen Set and Choose i=2

Recurse to backtrack(start=2) to fix the last position with the current array state. Initialize an empty 'seen' set at start=2 to track duplicates. Choose index i=2 to fix at position start=2. Since nums[2]=1 is not in 'seen', add it and swap nums[2] with nums[2] (no change).

💡 Recursion continues to complete the permutation. Duplicate tracking resets at each recursion level. Fixing the last element completes the permutation branch.

Line:

backtrack(start + 1)
seen = set()
if nums[i] not in seen:
    seen.add(nums[i])
    nums[start], nums[i] = nums[i], nums[start]

💡 Recursion depth increases to finalize the permutation. Duplicate skipping is local to recursion depth. Completing the permutation with the current prefix.

reconstruct

Add Complete Permutation [2,1,1] to Results and Backtrack to start=2 and start=1

Since start equals the length of nums, add the complete permutation [2,1,1] to the results list. Backtrack by swapping nums[2] and nums[2] back to restore the array to [2,1,1]. Then backtrack by swapping nums[1] and nums[1] back to restore the array to [2,1,1].

💡 Leaf node reached; collect the final unique permutation. Restore state to explore other choices at start=2 and start=1.

Line:

if start == len(nums):
    res.append(nums[:])
    return
nums[start], nums[i] = nums[i], nums[start]

💡 All unique permutations have now been found and recorded. Backtracking enables full exploration of the recursion tree and returns to previous recursion levels.

delete

Backtrack to start=0, Undo Swap and Complete Exploration

Backtrack by swapping nums[0] and nums[0] back to restore the array to [1,1,2]. This restores the initial state after exploring all branches starting with the first element, completing the exploration of all unique permutations.

💡 Restore initial state after exploring all branches starting with first element. Backtracking completes exploration of all unique permutations.

Line:

nums[start], nums[i] = nums[i], nums[start]

💡 Backtracking completes exploration of all unique permutations.

from typing import List

def permuteUnique(nums: List[int]) -> List[List[int]]:
    nums.sort()  # STEP 1
    res = []
    def backtrack(start=0):
        if start == len(nums):  # STEP 6,9,14
            res.append(nums[:])
            return
        seen = set()  # STEP 2,3,4,7,8,11,12,13
        for i in range(start, len(nums)):
            if nums[i] in seen:  # STEP 10
                continue
            seen.add(nums[i])  # STEP 2,3,4,7,8,11,12,13
            nums[start], nums[i] = nums[i], nums[start]  # STEP 2,3,4,7,8,11,12,13
            backtrack(start + 1)  # STEP 3,4,7,8,11,12,13
            nums[start], nums[i] = nums[i], nums[start]  # STEP 6,9,14
    backtrack()  # STEP 1
    return res

if __name__ == '__main__':
    print(permuteUnique([1,1,2]))

📊

Permutations II (With Duplicates) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step execution reveals how sorting and skipping duplicates at each recursion level efficiently prune redundant branches, which is hard to grasp from code alone.

enteringnums=[1,1,2]start=0

Call Path (current → root)

backtrack(start=0)

choosingnums=[1,1,2]start=0

Call Path (current → root)

backtrack(start=0)

Tried

i=0

Remaining

i=1i=2

Partial: [1]

choosingnums=[1,1,2]start=1

Call Path (current → root)

backtrack(start=1)

backtrack(start=0)

Remaining

i=1i=2

Partial: [1]

choosingnums=[1,1,2]start=2

Call Path (current → root)

backtrack(start=2)

backtrack(start=1)

backtrack(start=0)

Remaining

i=2

Partial: [1, 1]

choosingnums=[1,1,2]start=2

Call Path (current → root)

backtrack(start=2)

backtrack(start=1)

backtrack(start=0)

Tried

i=2

Partial: [1, 1, 2]

choosingnums=[1,1,2]start=2

Call Path (current → root)

backtrack(start=2)

backtrack(start=1)

backtrack(start=0)

Tried

i=2

Partial: [1, 1]

Found 1: [1,1,2]

choosingnums=[1,2,1]start=1

Call Path (current → root)

backtrack(start=1)

backtrack(start=0)

Tried

i=1i=2

Partial: [1, 2]

Found 1: [1,1,2]

choosingnums=[1,2,1]start=2

Call Path (current → root)

backtrack(start=2)

backtrack(start=1)

backtrack(start=0)

Tried

i=2

Partial: [1, 2, 1]

Found 1: [1,1,2]

choosingnums=[1,2,1]start=2

Call Path (current → root)

backtrack(start=2)

backtrack(start=1)

backtrack(start=0)

Tried

i=2

Partial: [1, 2]

Found 2: [1,1,2] [1,2,1]

choosingnums=[1,1,2]start=0

Call Path (current → root)

backtrack(start=0)

Tried

i=0

Remaining

i=2

✂ nums[1]=1 already fixed at this level

Found 2: [1,1,2] [1,2,1]

enteringnums=[2,1,1]start=1

Call Path (current → root)

backtrack(start=1)

backtrack(start=0)

Tried

i=0i=2

Partial: [2]

Found 2: [1,1,2] [1,2,1]

choosingnums=[2,1,1]start=1

Call Path (current → root)

backtrack(start=1)

backtrack(start=0)

Tried

i=1

Remaining

i=2

Partial: [2, 1]

Found 2: [1,1,2] [1,2,1]

choosingnums=[2,1,1]start=2

Call Path (current → root)

backtrack(start=2)

backtrack(start=1)

backtrack(start=0)

Tried

i=2

Partial: [2, 1, 1]

Found 2: [1,1,2] [1,2,1]

backtrackingnums=[2,1,1]start=1

Call Path (current → root)

backtrack(start=0)

Tried

i=0i=2

Found 3: [1,2,1] [2,1,1]

backtrackingnums=[1,1,2]start=0

Call Path (current → root)

root call

Tried

i=0i=2

Found 3: [1,2,1] [2,1,1]

Key Takeaways

✓ Sorting the input array is crucial to group duplicates and enable efficient skipping of repeated elements at each recursion level.

Without sorting, detecting duplicates to prune branches would be much harder and less efficient.

✓ The 'seen' set at each recursion level tracks which elements have been fixed at that position, preventing duplicate permutations by skipping repeated elements.

This local duplicate tracking is the key insight that avoids generating redundant permutations.

✓ Backtracking with swapping and undoing swaps restores the array state after exploring each branch, allowing the algorithm to systematically explore all unique permutations.

Understanding how backtracking restores state is essential to grasp how the recursion tree is fully explored without side effects.

Practice

1. You are given a string containing parentheses and letters. The goal is to remove the minimum number of parentheses to make the string valid (balanced parentheses) and return all possible results. Which algorithmic approach guarantees finding all valid strings with the minimum removals efficiently?

easy

A. Greedy approach that removes invalid parentheses from left to right without backtracking

B. Dynamic Programming that counts valid substrings and reconstructs solutions

C. Breadth-First Search (BFS) that explores all strings by removing one parenthesis at a time level-by-level

D. Brute force generating all subsequences and checking validity

Solution

1. Step 1: Understand problem constraints

   The problem requires minimal removals and all valid results, so partial or greedy removal may miss some minimal solutions.

2. Step 2: Analyze BFS approach

   BFS explores all strings by removing one parenthesis at a time, level-by-level, ensuring the first valid strings found have minimal removals and all such strings are collected.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   BFS guarantees minimal removals and completeness [OK]

Hint: Minimal removals require level-by-level BFS [OK]

Common Mistakes:

• Greedy misses some minimal solutions
• Brute force is correct but inefficient
• DP doesn't apply directly here

2. What is the time complexity of the bitmask-optimized backtracking solution for the N-Queens problem, and why is the common misconception that it is O(n^3) incorrect?

medium

A. O(n^3) because there are three nested loops over rows, columns, and diagonals

B. O(2^n) because bitmasking iterates over all subsets of columns

C. O(n!) because each row places one queen and pruning reduces the search space factorially

D. O(n^2) because each queen placement checks all previous rows and columns

Solution

1. Step 1: Identify the branching factor per row

   Each row places exactly one queen, and pruning avoids invalid columns and diagonals, reducing choices drastically.

2. Step 2: Understand factorial growth

   Because queens cannot share columns, the number of ways to place queens is at most n!; pruning reduces this further but worst-case remains O(n!).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask pruning reduces search to permutations of columns [OK]

Hint: N-Queens search space is permutations, not polynomial loops [OK]

Common Mistakes:

• Assuming nested loops imply cubic time
• Confusing bitmask subsets with full subsets
• Ignoring pruning effect

3. Examine the following code snippet for the Word Search problem. It is almost correct but contains one subtle bug. Identify the line causing the bug.

medium

A. Line where board[r][c] = temp is restored after recursion

B. Line where temp = board[r][c]

C. Line where directions are defined

D. Line missing board[r][c] = '#' to mark visited

Solution

1. Step 1: Identify missing visited marking

   The code does not mark the current cell as visited before recursive calls, allowing revisits.

2. Step 2: Understand impact of missing marking

   Without marking, dfs can revisit the same cell multiple times, causing incorrect matches or infinite loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Marking visited cells is essential to prevent reuse [OK]

Hint: Check if visited cells are marked before recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Restoring cell too early

4. Suppose the problem is modified so that digits can be repeated any number of times (reuse allowed), and you want to generate all letter combinations of length n from the given digits. Which modification to the algorithm correctly handles this reuse scenario?

hard

A. Modify backtracking to allow choosing the same digit multiple times by not incrementing the index after each choice until length n is reached

B. Sort digits and generate combinations by picking letters only once per digit

C. Use dynamic programming to store combinations of length k and build up to length n without reuse

D. Use the same iterative queue approach but do not advance the digit index; instead, for each combination, append letters from all digits repeatedly until length n is reached

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means digits can be chosen multiple times to build combinations of length n.

2. Step 2: Identify correct approach

   Backtracking can be modified to not increment the digit index after choosing a letter, allowing reuse until length n is reached.

3. Step 3: Why other options fail

   Iterative queue approach as-is assumes fixed digit positions; DP without reuse does not handle repeated digits; sorting and picking once per digit ignores reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with flexible index handles reuse elegantly [OK]

Hint: Backtracking index controls reuse by not advancing [OK]

Common Mistakes:

• Trying to reuse digits in iterative approach without index control
• Ignoring reuse in DP or sorting

5. Suppose the problem is modified so that IP address segments can be reused multiple times (i.e., segments can overlap and be repeated). Which modification to the backtracking algorithm correctly handles this variant without generating duplicates or invalid IPs?

hard

A. Remove the pruning condition on remaining characters and segments to allow overlapping segments

B. Use a memoization cache keyed by (start, segments formed) to avoid recomputing paths

C. Allow segments to be reused by resetting start index to previous segment start after each addition

D. Change the algorithm to generate all permutations of segments without pruning

Solution

1. Step 1: Understand reuse implies overlapping segments

   Allowing reuse means the same substring can be used multiple times, potentially causing repeated computations.

2. Step 2: Apply memoization to avoid duplicates

   Memoization keyed by (start, segments formed) prevents recomputing the same subproblems and avoids duplicates.

3. Step 3: Evaluate other options

   Removing pruning causes inefficiency; resetting start index breaks segment order; generating all permutations ignores validity and pruning.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Memoization efficiently handles reuse without duplicates [OK]

Hint: Memoization avoids recomputation when segments can be reused [OK]

Common Mistakes:

• Removing pruning causes timeouts
• Resetting start index breaks segment order