Pattern #23

Permutations

Important interview questions, thinking patterns, N! ordering generation, Used Array vs Swap methods, Next Permutation algorithm, and Go rules.

Must Solve

14 core questions — solve these first.

1.Permutations
Unused elements choice + used[] boolean arraymedium
2.Permutations II
Sort array + skip duplicate choice at same depth (!used[i-1])medium
3.Next Permutation
Single-pass scan right-to-left -> swap -> reverse suffixmedium
4.Permutation Sequence
Factorial block division index calculationhard
5.Letter Case Permutation
Toggle uppercase / lowercase character branchingmedium
6.Letter Combinations of a Phone Number
Digit mapping backtracking permutationmedium
7.Generate Parentheses
Open/close count permutation backtrackingmedium
8.Beautiful Arrangement
Divisibility rule checking backtracking choicemedium
9.Palindrome Permutation II
Generate half string permutations + mirrormedium
10.Letter Tile Possibilities
Character frequency map unique permutationsmedium
11.N-Queens
Column permutation placement + diagonal checkhard
12.String Permutations
Generate all unique string permutationsmedium
13.Find All Anagrams in a String
Sliding window character permutation matchingmedium
14.Permutation in String
Sliding window frequency check for s1 in s2medium

Also Important

8 more questions worth practicing.

15.Combinations
N choose K start index combinationsmedium
16.Combination Sum
Reusable numbers combination backtrackingmedium
17.Subsets
Take or Skip power set generationmedium
18.Subsets II
Sort + skip duplicates power setmedium
19.Maximum Compatibility Score Sum
Student-Mentor pairing permutationsmedium
20.Number of Squareful Arrays
Permutations with perfect square adjacent sumhard
21.Construct Smallest Number From DI String
Decreasing/Increasing pattern permutation searchmedium
22.Minimum Number of Work Sessions to Finish the Tasks
Backtracking / Bitmask DP task assignmentmedium

How to Think

Does order matter?Permutation ([1,2] != [2,1])
Need every possible ordering?Backtracking (N! possibilities)
Need choose one unused item at each position?used[] boolean array or swap
Input contains duplicates?Sort + skip duplicate starting choices

Go Permutations Template (Used-Array Approach)

Standard Used Array Permutations Template in Go

func permute(nums []int) [][]int {
    results := [][]int{}
    path := []int{}
    used := make([]bool, len(nums))

    var dfs func()
    dfs = func() {
        if len(path) == len(nums) {
            copyPath := append([]int(nil), path...)
            results = append(results, copyPath)
            return
        }

        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }

            used[i] = true
            path = append(path, nums[i])

            dfs()

            path = path[:len(path)-1] // Undo path
            used[i] = false          // Undo used
        }
    }

    dfs()
    return results
}

👉 Total Time: O(N × N!) | Space: O(N) (Recursion depth = N)

Two Implementation Methods

Method 1: Used Array

used[i] = true → Recurse → used[i] = false

Keep an explicit boolean array used[] tracking availability. Clean and easy to handle duplicates!

Method 2: In-Place Swap

swap(nums[i], nums[j]) → Recurse → swap back

Fix current position, swap remaining items into position, and backtrack by swapping back.

Next Permutation Algorithm

To find the lexicographically next greater permutation in-place in O(N) time & O(1) space without generating all permutations:

1. Scan right-to-left to find first decreasing point: nums[i] < nums[i+1]
2. Scan right-to-left to find slightly larger value: nums[j] > nums[i]
3. Swap nums[i] and nums[j]
4. Reverse the suffix from index i+1 to end

👉 Example: [1, 2, 3] → Next Permutation is [1, 3, 2]

Visual Memory Rule

Order Matters!  →  [1, 2] != [2, 1]
N elements     →  N! total orderings (3! = 6, 5! = 120, 10! = 3.6M)
Duplicates     →  Sort input + skip: if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue

💡 Golden Rule: "Fill one position at a time using one unused value, then undo and try another ordering."

Common Interview Mistakes

1. Reusing Same Value

Generating [1, 1, 2] from [1, 2, 3] because of missing used[i] checks.

2. Forgetting Undo Unmark

Setting used[i] = true but forgetting used[i] = false after returning from recursive call.

3. Confusing Permutation with Combination

Subsets / Combinations choose WHAT (order doesn't matter). Permutations choose WHAT + WHERE (order DOES matter!).

4. Not Copying Path in Go

Saving path without copy causes later backtracking pops to mutate saved results!

Interview Rules

1. Order matters? → Permutation
2. Every possible ordering? → Backtracking
3. At each position → Choose unused item (used[] boolean array)
4. Alternative implementation → In-place swap + recurse + swap back
5. Duplicate input? → Sort first + skip duplicate choices
6. N unique items → N! total permutations
7. Next lexicographical order? → Next Permutation algorithm
8. Overall Complexity → O(N × N!) time, O(N) space

Small Rules

Rule 1: For N unique elements, there are strictly N! permutations.
Rule 2: Permutation count grows exponentially fast (5! = 120, 10! = 3.6M).
Rule 3: Recursion depth is O(N) because permutation length is N.
Rule 4: Copying each completed permutation of length N makes total work O(N × N!).
Rule 5: Always copy path before appending to result slice in Go.

Production Thinking

Task Deployment Execution Order → 3 deployment steps (A, B, C) = 3! = 6 possible execution sequences

E2E Testing Workflow Order → Testing different operation sequences (Login -> Update -> Logout) exposes state bugs

Slot Job Scheduling → Assigning jobs into ordered execution slots with different priority rules

Production Warning → Factorial growth: 10! is ~3.6M, 15! is billions! Never generate all permutations in production; use greedy/DP/pruning instead.

Remember This

Permutation            → Order matters
At each position       → Choose unused value
Choose                 → Mark used
Explore                → Recurse
Undo                   → Unmark
Unique n items         → n!
Duplicates             → Sort + skip
Large n                → Very expensive

💡 Golden Rule: "Fill one position at a time using one unused value, then undo and try another ordering."