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 only digits. Your task is to split it into exactly four parts such that each part represents a valid IP address segment (0 to 255, no leading zeros except for '0'). Which algorithmic approach guarantees finding all valid IP addresses efficiently?

easy

A. Sorting the digits and then partitioning into four segments

B. Greedy approach that picks the shortest valid segment at each step

C. Dynamic programming to count the number of valid segmentations

D. Backtracking with pruning to explore all valid segmentations

Solution

1. Step 1: Understand the problem constraints

   The problem requires enumerating all valid IP addresses, which involves exploring multiple segmentations of the string.

2. Step 2: Evaluate algorithm suitability

   Greedy approaches fail because they may miss valid segmentations; DP counting does not generate all solutions; sorting digits destroys original order. Backtracking with pruning systematically explores all valid partitions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking explores all partitions with pruning to avoid invalid segments [OK]

Hint: Backtracking explores all segmentations with pruning [OK]

Common Mistakes:

• Assuming greedy can find all valid IPs
• Using DP counting without generating solutions

2. What is the time complexity of the optimal backtracking solution for the Expression Add Operators problem, where n is the length of the input string? Assume the solution tries all operator insertions and substring splits with pruning and efficient string building.

medium

A. O(4^n) because at each position there are up to 4 choices (3 operators + no operator split)

B. O(n * 3^n) because each digit can be combined with 3 operators and substring splits

C. O(2^n) since only two operators are considered at each step

D. O(n^3) due to substring parsing and operator insertions

Solution

1. Step 1: Identify branching factor per digit

   At each digit, we can insert one of 3 operators (+, -, *) or choose to extend the current operand (no operator), but the main branching factor is 3 operators per split, and substring splits add a factor of n.

2. Step 2: Calculate total complexity

   The total complexity is roughly O(n * 3^n) because for each of the n positions, there are up to 3 operator choices, and substring splits add an n factor.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Exponential branching with 3 operators and substring splits [OK]

Hint: 3 operators per digit and substring splits lead to O(n * 3^n) complexity [OK]

Common Mistakes:

• Confusing substring parsing cost as cubic
• Assuming only 2 operators reduce complexity
• Miscounting branching factor as 4

3. Examine the following buggy code snippet for Expression Add Operators. Which line contains the subtle bug that causes incorrect results on inputs with leading zeros?

def addOperators(num: str, target: int) -> List[str]:
    res = []
    path = []
    def backtrack(index: int, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(''.join(path))
            return
        for i in range(index, len(num)):
            # Bug: missing leading zero check
            curr_str = num[index:i+1]
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)
                backtrack(i+1, curr, curr)
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)
                backtrack(i+1, evaluated + curr, curr)
                path[length_before:] = []
    backtrack(0, 0, 0)
    return res

medium

A. Line with 'if i != index and num[index] == '0':' missing here

B. Line with 'curr_str = num[index:i+1]' (substring extraction)

C. Line with 'path[length_before:] = []' (backtracking cleanup)

D. Line with 'path.append('+'); path.append(curr_str)' (operator insertion)

Solution

1. Step 1: Identify handling of leading zeros

   The code lacks the check 'if i != index and num[index] == '0': break' which prevents invalid operands like "05".

2. Step 2: Confirm bug location

   This missing check is critical and should be placed before parsing curr_str to avoid invalid expressions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check causes invalid operands [OK]

Hint: Leading zero check missing causes invalid operands [OK]

Common Mistakes:

• Confusing backtracking cleanup lines as bug
• Thinking substring extraction is buggy

4. What is the time complexity of the optimal in-place next permutation algorithm for an input array of length n?

medium

A. O(n) because it scans the array a constant number of times

B. O(n log n) because it sorts the suffix after the pivot

C. O(n!) due to generating all permutations

D. O(n^2) because it swaps elements multiple times in nested loops

Solution

1. Step 1: Identify the main operations

   The algorithm scans from the end to find the pivot (O(n)), then scans again to find the swap element (O(n)), and finally reverses the suffix (O(n)).

2. Step 2: Sum up the operations

   All steps are linear scans or swaps, so total time complexity is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No sorting or factorial generation involved, linear scans only [OK]

Hint: Next permutation scans array linearly multiple times [OK]

Common Mistakes:

• Confusing suffix reversal with sorting
• Assuming factorial due to permutations

5. What is the time complexity of the optimal backtracking with Trie approach for Word Search II, given a board of size MxN and a list of words with maximum length L? Assume the Trie is already built.

medium

A. O(M * N * 4 * 3^(L-1)) due to pruning and adjacency constraints

B. O(M * N * 4^L * W), where W is the number of words

C. O(M * N * L^2) because each cell explores all prefixes

D. O(M * N * L) since each cell is visited once per character

Solution

1. Step 1: Identify branching factor in backtracking

   From each cell, up to 4 directions are possible initially, then up to 3 directions for subsequent steps due to no revisiting.

2. Step 2: Calculate complexity with pruning

   Trie pruning reduces unnecessary paths, so complexity is roughly O(M * N * 4 * 3^(L-1)) where L is max word length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known complexity from Trie + backtracking analysis [OK]

Hint: Branching factor reduces after first step due to visited constraints [OK]

Common Mistakes:

• Confusing W (number of words) as multiplicative factor in optimal approach.