Permutations

▶

Steps

setup

Initialize result and counters

The algorithm starts by copying the input array [1,2,3] into the results list and initializing the counters array c with zeros for each element.

💡 This setup is crucial because the counters track how many times each element has been swapped, enabling the algorithm to generate permutations without recursion.

Line:

res = [nums[:]]
c = [0] * len(nums)
i = 0

💡 The initial permutation is always included, and counters start at zero to track swaps per element.

compare

Check counter c[0] < 0 (i=0)

The algorithm checks if c[0] < 0, which is false since c[0] = 0 and 0 is not less than 0, so it moves to reset c[0] and increment i.

💡 This comparison determines whether to perform a swap or move to the next index; since c[0] is not less than i, no swap occurs here.

Line:

if c[i] < i:

💡 When counters equal or exceed i, the algorithm resets the counter and moves forward, controlling swap frequency.

shrink

Reset counter c[0] and increment i to 1

Since no swap was done at i=0, the algorithm resets c[0] to 0 (already zero) and increments i to 1 to check the next position.

💡 Resetting counters and moving forward ensures the algorithm explores swaps at higher indices systematically.

Line:

else:
    c[i] = 0
    i += 1

💡 Incrementing i moves the algorithm to consider swaps involving the next element.

compare

Check counter c[1] < 1 (i=1)

The algorithm checks if c[1] < 1, which is true since c[1] = 0, so it proceeds to perform a swap based on i's parity.

💡 This condition triggers a swap to generate a new permutation by exchanging elements at positions 0 and 1 because i is odd/even.

Line:

if c[i] < i:

💡 Counters control when swaps happen, ensuring each element is swapped the correct number of times.

insert

Swap nums[c[1]] and nums[1] because i is odd

Since i=1 is odd, swap elements at indices c[1]=0 and i=1, swapping nums[0] and nums[1], changing array to [2,1,3].

💡 Swapping elements creates a new permutation; the parity of i determines which elements to swap for systematic coverage.

Line:

if i % 2 == 0:
    nums[0], nums[i] = nums[i], nums[0]
else:
    nums[c[i]], nums[i] = nums[i], nums[c[i]]

💡 Parity-based swapping ensures all permutations are generated without repetition.

insert

Add new permutation [2,1,3] to results

After swapping, the new permutation [2,1,3] is appended to the results list.

💡 Each swap produces a unique permutation that must be saved to the results for the final output.

Line:

res.append(nums[:])

💡 Storing a copy of the current array state preserves the permutation before further changes.

shrink

Increment counter c[1] and reset i to 0

The counter c[1] is incremented from 0 to 1, and i is reset to 0 to restart the process from the beginning.

💡 Incrementing counters tracks how many swaps have been done at each position; resetting i restarts the iteration to explore new swaps.

Line:

c[i] += 1
i = 0

💡 Resetting i ensures the algorithm revisits earlier positions to generate all permutations systematically.

compare

Check counter c[0] < 0 (i=0) again

At i=0, the algorithm checks if c[0] < 0, which is false, so it resets c[0] and increments i to 1 again.

💡 This step repeats the initial check to continue the permutation generation cycle.

Line:

if c[i] < i:

💡 The algorithm cycles through indices, checking counters to decide swaps or increments.

shrink

Reset counter c[0] and increment i to 1

No swap at i=0, so c[0] is reset to 0 and i increments to 1 to check the next position.

💡 This step moves the algorithm forward to explore swaps at i=1 again.

Line:

else:
    c[i] = 0
    i += 1

💡 Incrementing i advances the algorithm's exploration of permutations.

compare

Check counter c[1] < 1 (i=1) again

Now c[1] = 1, which is not less than i=1, so no swap occurs; the algorithm resets c[1] and increments i to 2.

💡 This check prevents repeated swaps at the same position beyond allowed times.

Line:

if c[i] < i:

💡 Counters limit swaps to ensure all permutations are unique and complete.

shrink

Reset counter c[1] and increment i to 2

Since no swap at i=1, c[1] is reset to 0 and i increments to 2 to check swaps at the last index.

💡 Moving to the last index allows the algorithm to explore final swaps for permutations.

Line:

else:
    c[i] = 0
    i += 1

💡 Incrementing i to the last index prepares for final swaps in the permutation sequence.

compare

Check counter c[2] < 2 (i=2)

The algorithm checks if c[2] < 2, which is true since c[2] = 0, so it proceeds to swap elements based on i's parity.

💡 This condition triggers swaps involving the last element to generate new permutations.

Line:

if c[i] < i:

💡 Swaps at the last index complete the permutation generation cycle.

insert

Swap nums[0] and nums[2] because i is even

Since i=2 is even, swap elements at indices 0 and 2, changing array from [2,1,3] to [3,1,2].

💡 Parity-based swapping continues to generate new permutations by exchanging elements at strategic positions.

Line:

if i % 2 == 0:
    nums[0], nums[i] = nums[i], nums[0]

💡 Swapping the first and last elements creates a new permutation distinct from previous ones.

insert

Add new permutation [3,1,2] to results

The new permutation [3,1,2] is appended to the results list after the swap.

💡 Each new permutation must be saved immediately to preserve the sequence generated by swaps.

Line:

res.append(nums[:])

💡 Appending a copy of the current array state ensures the permutation is recorded before further changes.

shrink

Increment counter c[2] and reset i to 0

Counter c[2] is incremented from 0 to 1, and i is reset to 0 to restart the iteration from the beginning.

💡 Incrementing counters and resetting i allows the algorithm to explore new swaps from the start.

Line:

c[i] += 1
i = 0

💡 This control flow ensures all permutations are generated by revisiting earlier indices.

compare

Check counter c[0] < 0 (i=0) again

At i=0, c[0] < 0 is false, so the algorithm resets c[0] and increments i to 1.

💡 This repeated check controls the iteration flow through the array indices.

Line:

if c[i] < i:

💡 The algorithm cycles through indices, checking counters to decide swaps or increments.

shrink

Reset counter c[0] and increment i to 1

No swap at i=0, so c[0] is reset and i increments to 1 to check the next position.

💡 Incrementing i advances the algorithm's exploration of permutations.

Line:

else:
    c[i] = 0
    i += 1

💡 Incrementing i moves the algorithm forward systematically.

compare

Check counter c[1] < 1 (i=1)

At i=1, c[1] = 0 which is less than 1, so the algorithm will perform a swap.

💡 This triggers a swap to generate a new permutation by exchanging elements at positions 0 and 1.

Line:

if c[i] < i:

💡 Counters control when swaps happen, ensuring each element is swapped the correct number of times.

insert

Swap nums[c[1]] and nums[1] because i is odd

Since i=1 is odd, swap elements at indices c[1]=0 and i=1, swapping nums[0] and nums[1], changing array to [1,3,2].

💡 Swapping elements creates a new permutation; the parity of i determines which elements to swap for systematic coverage.

Line:

else:
    nums[c[i]], nums[i] = nums[i], nums[c[i]]

💡 Parity-based swapping ensures all permutations are generated without repetition.

insert

Add new permutation [1,3,2] to results

The new permutation [1,3,2] is appended to the results list after the swap.

💡 Each new permutation must be saved immediately to preserve the sequence generated by swaps.

Line:

res.append(nums[:])

💡 Appending a copy of the current array state ensures the permutation is recorded before further changes.

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    res = [nums[:]]  # STEP 1: Initialize result with original array
    c = [0] * len(nums)  # STEP 1: Initialize counters
    i = 0  # STEP 1: Start index
    while i < len(nums):  # STEP 2-20: Loop through indices
        if c[i] < i:  # STEP 2,4,10,12,18: Check if swap needed
            if i % 2 == 0:  # STEP 5,13: Even index swap
                nums[0], nums[i] = nums[i], nums[0]  # STEP 5,13: Swap elements
            else:  # STEP 5,19: Odd index swap
                nums[c[i]], nums[i] = nums[i], nums[c[i]]  # STEP 5,19: Swap elements
            res.append(nums[:])  # STEP 6,14,20: Append new permutation
            c[i] += 1  # STEP 7,15: Increment counter
            i = 0  # STEP 7,15: Reset index
        else:  # STEP 3,9,11,17: Reset counter and increment index
            c[i] = 0
            i += 1
    return res

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

📊

Permutations - Watch the Algorithm Execute, Step by Step

Watching each swap and counter update reveals how Heap's algorithm efficiently produces permutations without recursion, making the process clear and intuitive.

enteringnums=[1,2,3]

Call Path (current → root)

permute([1,2,3])

Found 1: [1,2,3]

choosingnums=[1,2,3]

Call Path (current → root)

permute([1,2,3])

Tried

no swap at i=0

Remaining

reset c[0], increment i

Found 1: [1,2,3]

backtrackingnums=[1,2,3]

Call Path (current → root)

permute([1,2,3])

Tried

reset c[0], increment i

Remaining

check c[1] < 1

Found 1: [1,2,3]

choosingnums=[1,2,3]

Call Path (current → root)

permute([1,2,3])

Tried

swap at i=1

Found 1: [1,2,3]

choosingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

swap nums[0] and nums[1]

Found 1: [1,2,3]

backtrackingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

added [2,1,3]

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

backtrackingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

increment c[1], reset i

Remaining

check c[0] < 0

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

choosingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

no swap at i=0

Remaining

reset c[0], increment i

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

backtrackingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

reset c[0], increment i

Remaining

check c[1] < 1

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

choosingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

no swap at i=1

Remaining

reset c[1], increment i

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

backtrackingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

reset c[1], increment i

Remaining

check c[2] < 2

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

choosingnums=[2,1,3]

Call Path (current → root)

permute([1,2,3])

Tried

swap at i=2

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

choosingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

swap nums[0] and nums[2]

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

backtrackingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

added [3,1,2]

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

backtrackingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

increment c[2], reset i

Remaining

check c[0] < 0

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

choosingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

no swap at i=0

Remaining

reset c[0], increment i

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

backtrackingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

reset c[0], increment i

Remaining

check c[1] < 1

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

choosingnums=[3,1,2]

Call Path (current → root)

permute([1,2,3])

Tried

swap at i=1

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

choosingnums=[1,3,2]

Call Path (current → root)

permute([1,2,3])

Tried

swap nums[0] and nums[1]

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

backtrackingnums=[1,3,2]

Call Path (current → root)

permute([1,2,3])

Tried

added [1,3,2]

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

Key Takeaways

✓ Heap's algorithm uses counters and parity-based swaps to generate all permutations efficiently without recursion.

This insight is hard to see from code alone because the counters' role and parity-based swapping logic are subtle and intertwined.

✓ The counters array controls how many times each element is swapped, ensuring no duplicate permutations and systematic coverage.

Understanding counters' gating role clarifies why the algorithm resets and increments indices, which is not obvious from reading code.

✓ Swapping elements based on whether the current index is even or odd ensures all permutations are generated by minimal swaps.

The parity-based swap decision is a key branching point that determines the swap pattern, which is clearer when visualized step-by-step.

Practice

1. Given the following code for next permutation, what is the content of the array nums after calling next_permutation([1, 3, 2])?

easy

A. [1, 2, 3]

B. [2, 3, 1]

C. [2, 1, 3]

D. [1, 3, 2]

Solution

1. Step 1: Trace the pivot search

   Start with i = 1 (index of 3). Since nums[1]=3 >= nums[2]=2, decrement i to 0. nums[0]=1 < nums[1]=3, so pivot i=0.

2. Step 2: Find j to swap with pivot

   Start j=2 (value 2). nums[2]=2 > nums[0]=1, so j=2. Swap nums[0] and nums[2]: array becomes [2,3,1]. Then reverse suffix from i+1=1 to end: reverse [3,1] -> [1,3]. Final array: [2,1,3].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Array changes from [1,3,2] to [2,1,3] after next permutation [OK]

Hint: Pivot found at first decreasing from right, swap and reverse suffix [OK]

Common Mistakes:

• Swapping with wrong element
• Not reversing suffix after swap

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. Consider this modified code snippet for generating parentheses. Which line contains a subtle bug that can cause invalid sequences to be generated?

medium

A. Line with 'if close_count <= open_count:' condition

B. Line with 's.pop()' after backtrack calls

C. Line with 'if open_count < n:' condition

D. Line with 'if len(s) == 2 * n:' base case

Solution

1. Step 1: Examine close_count condition

   The condition 'close_count <= open_count' allows adding ')' even when close_count equals open_count, which can produce invalid sequences.

2. Step 2: Correct condition

   The correct condition is 'close_count < open_count' to ensure ')' is added only when there are unmatched '('.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes invalid sequence generation [OK]

Hint: Close count must be strictly less than open count [OK]

Common Mistakes:

• Using <= instead of < for close_count condition
• Forgetting to pop after recursion

4. What is the time complexity of the optimal backtracking algorithm that generates unique permutations of an array with duplicates by sorting and skipping duplicates during recursion?

medium

A. O(n! * log n) due to sorting and binary search for duplicates

B. O(n! * n^2) because each permutation requires copying the array and checking duplicates

C. O(n^n) because the recursion explores all possible swaps without pruning

D. O(n! * n) because pruning duplicates early reduces redundant branches but each permutation still requires O(n) copying

Solution

1. Step 1: Identify complexity of outer and inner loops

   Backtracking explores permutations, which is O(n!). Each permutation requires copying O(n) elements to result.

2. Step 2: Check if pruning duplicates reduces complexity

   Pruning duplicates early avoids redundant branches, so complexity is O(n! * n), not worse. Sorting is O(n log n) but done once.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Pruning reduces branches but copying each permutation costs O(n) [OK]

Hint: Pruning duplicates reduces branches but copying costs O(n) per permutation [OK]

Common Mistakes:

• Confusing pruning effect or ignoring copy cost

5. Examine the following snippet from an optimized Sudoku solver. Which line contains a subtle bug that can cause incorrect solutions or failure to backtrack properly?

def backtrack():
    if not empties:
        return True
    empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
    r, c = empties[0]
    for ch in get_candidates(r, c):
        board[r][c] = ch
        rows[r].add(ch)
        cols[c].add(ch)
        boxes[(r//3)*3 + c//3].add(ch)
        empties.pop(0)
        if backtrack():
            return True
        # Undo changes
        board[r][c] = '.'
        rows[r].remove(ch)
        cols[c].remove(ch)
        boxes[(r//3)*3 + c//3].remove(ch)
        empties.insert(0, (r, c))
    return False

medium

A. Line that pops the first empty cell from empties

B. Line that sorts empties by candidate count

C. Line that adds ch to rows[r]

D. Line that resets board[r][c] to '.' after backtracking

Solution

1. Step 1: Identify mutation of empties list

   The line popping empties[0] removes the cell but is never restored on backtrack failure.

2. Step 2: Consequence of missing restoration

   Without re-adding the cell to empties after failed recursion, future calls miss this cell, causing incorrect state and solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking requires undoing all changes including empties list [OK]

Hint: Backtracking must undo all state changes, including empties list [OK]

Common Mistakes:

• Forgetting to restore empties after pop
• Assuming board reset is sufficient