Skip to content

Volume ITechnology

4.18.3 — Permutations ​

LeetCode 46 · Medium · ★ Blind 75

The problem ​

Return every ordering of the array. All values are distinct.

[1,2,3]  →  [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

n is at most 6, so at most 6! = 720 results.

The pattern ​

This is the third loop shape, and the difference from combinations is one sentence:

Order matters, so [1,2] and [2,1] are both answers.

Think of this like arranging 3 specific books on a shelf. You must use all 3 books, and putting them in the order A-B-C is a completely different arrangement than C-B-A. Because every book must be used exactly once per arrangement, we can't just move forward blindly—we need to be able to pick any book that hasn't been placed on the shelf yet, regardless of where it started in the pile.

That kills the start index. In 4.18.1 and 4.18.2, the loop ran from start forwards precisely to stop both orderings being generated. Here you want both, so the loop runs over everything — and you need a different way to avoid using the same element twice within one permutation.

That way is a used-marker.

The tree:

                    []
        /            |            \
      [1]           [2]           [3]        3 choices
      / \           / \           / \
  [1,2] [1,3]  [2,1] [2,3]  [3,1] [3,2]      2 choices each
    |     |      |     |      |     |
 [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]  1 choice each

3 \times 2 \times 1 = 6 leaves. Only the leaves are answers, unlike subsets where every node was one.

The solution ​

python
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []  # (1)
        path = []
        used = [False] * len(nums)  # (2)

        def backtrack():  # (3)
            if len(path) == len(nums):        # (4) only full-length paths count
                result.append(path[:])
                return

            for i in range(len(nums)):        # (5) every element, every time
                if used[i]:  # (6)
                    continue

                used[i] = True  # (7)
                path.append(nums[i])  # (8)

                backtrack()  # (9)

                path.pop()                    # (10) undo both
                used[i] = False  # (11)

        backtrack()
        return result
ts
function permute(nums: number[]): number[][] {
  const result: number[][] = [];  // (1)
  const path: number[] = [];
  const used = new Array(nums.length).fill(false);  // (2)

  function backtrack(): void {  // (3)
    if (path.length === nums.length) {  // (4)
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {  // (5)
      if (used[i]) continue;  // (6)

      used[i] = true;  // (7)
      path.push(nums[i]);  // (8)

      backtrack();  // (9)

      path.pop();  // (10)
      used[i] = false;  // (11)
    }
  }

  backtrack();
  return result;
}

Line by line ​

(1) result collects the finished orderings, and path is the ordering being built.

(2) used[i] says whether element i is already in path. A permutation uses every element exactly once, so we must know which ones are taken.

(3) backtrack() fills the next position of path. It needs no arguments, because path and used hold everything.

(4) path is full, so it is one complete ordering. Save a copy and stop.

(5) Try every element for the next position, starting from 0 each time. Unlike subsets, order matters here: [1, 2] and [2, 1] are different permutations, so we must be allowed to look back at earlier elements.

(6) Skip elements already placed.

(7) Mark this element as used, and

(8) place it in the next position.

(9) Fill the remaining positions.

(10) Undo the placement, and

(11) mark the element as free again, so the next choice at this position starts from a clean state.

Two pieces of state, so two undos. path.pop() and used[i] = False must both happen. Forgetting the second is the classic bug here: elements stay marked as used and later branches find nothing available, so the output is short and mysteriously missing entries.

The base case checks length, not an index. A permutation is only complete when every element has been placed.

No start index anywhere. If you find yourself writing one in a permutation problem, you have the wrong shape.

The swap version ​

There is a neater-looking alternative that needs no used array. Swap the current position with each candidate, recurse, then swap back.

python
def permute(self, nums):
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]     # choose
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]     # undo
    backtrack(0)
    return result

It uses O(1) extra space beyond the output, since the array itself carries the state.

The catch: it does not produce the permutations in lexicographic order, and it becomes awkward when the input has duplicates, because the sorted-order needed for the duplicate skip is destroyed by the swaps. The used array version handles duplicates cleanly.

Prefer the used version. Mention the swap version as an alternative and say why you did not pick it.

Duplicates: Permutations II ​

LeetCode 47 allows repeated values, and asks for unique permutations only. Two changes:

python
nums.sort()                                                    # 1
...
for i in range(len(nums)):
    if used[i]:
        continue
    if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:    # 2
        continue

Read the second condition carefully, because it is the subtlest guard in the whole chapter.

not used[i-1] means the previous equal value has not been placed on this path. If it has not been placed, then choosing this copy now would produce exactly the arrangement that the earlier copy will produce when its turn comes — a duplicate among siblings.

If the previous copy has been placed, then this copy is legitimately the second one in the permutation, and it must be allowed.

Sorting first is what makes equal values adjacent so that nums[i] == nums[i-1] finds them.

Get this wrong in either direction and you either produce duplicates or lose valid answers. Trace [1,1,2] by hand once to see it.

Complexity ​

O(n! \times n) time — n! permutations, each costing O(n) to copy.

O(n) space for the recursion, the path and the used array.

The factorial is unavoidable: the output has n! entries.

Let's break this down:

  • Time Complexity: There are n! permutations (for the first spot you have n choices, for the second n-1, etc.). For each of these n! valid permutations (leaves of the tree), we make a full copy of the path array of length n. Thus, creating all copies takes O(n \cdot n!) time. The number of internal nodes in the tree is less than n!, so leaf copying dominates.
  • Space Complexity: The recursive call stack goes exactly n levels deep. The path and used arrays also take O(n) space. So auxiliary space is strictly O(n).

Edge cases ​

  • One element. One permutation, the element itself.
  • Two elements. Two permutations, [a, b] and [b, a].
  • Repeated values, like [1, 1, 2]. This code would print duplicate orderings. That is Permutations II, covered in the section above.

Where this goes next ​

  • Permutations II — above.
  • Next Permutation (LeetCode 31) — a completely different problem despite the name. It finds the single next permutation in dictionary order in O(n), with no recursion at all. Find the rightmost place where the numbers go up, swap it with the smallest larger value to its right, then reverse everything after it. A generator like itertools.permutations can produce orderings one at a time using a step much like this.
  • Letter Combinations of a Phone Number — a permutation-shaped problem where the choices at each position come from a lookup table. 4.18.8.
  • N-Queens — a permutation of column positions, with extra constraints. 4.18.9.

What the interviewer will push on ​

"Why no start index?" Order matters, so both [1,2] and [2,1] are wanted. A start index exists to suppress one of them.

"How many permutations are there?" n!, and say it before coding.

"You have two pieces of state — did you undo both?" Yes. This is asked because it is the common bug.

"What changes with duplicate values?" Sort, then the not used[i-1] guard, and be ready to explain what it means.

"Can you avoid the used array?" The swap version, at the cost of ordering and duplicate handling.

One thing to volunteer: state which of the three shapes you are using and why, in one sentence. "Order matters here, so it is the used-marker shape rather than the start-index shape."

Next: 4.18.4 Subsets II — the duplicate-skip rule in its cleanest form.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet