Skip to content

103 — Permutations

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

103 — Permutations

LeetCode 46 · Medium. Given an array nums of distinct integers, return all possible permutations. Return the answer in any order.

🍽️ Intuition

Subsets asked "in or out?" for each element, independently. Permutations asks a different question at every step: "which unused element goes next?" Order matters now, and every element must appear exactly once in every output — which means the search has to actively track what's already been used, not just where it left off in the array.

🚩 Pattern-Recognition Cue

"Return all possible permutations / arrangements / orderings" signals backtracking where the choice at each step is "pick any element I haven't used yet" rather than "pick any element from start onward." Whenever order distinguishes two otherwise-identical outputs ([1, 2] and [2, 1] both count separately), you need a used tracker instead of an advancing start index.

🐢 Brute Force

Generate every sequence of length n built from nums, including sequences that repeat an element and omit another — then filter, keeping only the sequences that happen to use each element exactly once. This is generate-then-filter at its most wasteful: the search tree has n^n leaves, and only n! of them survive the filter.

func permuteBruteForce(_ nums: [Int]) -> [[Int]] {
    var results: [[Int]] = []
    var path: [Int] = []

    func generate() {
        if path.count == nums.count {
            if Set(path).count == nums.count {   // filter: keep only if every element is distinct
                results.append(path)
            }
            return
        }

        for num in nums {
            path.append(num)
            generate()
            path.removeLast()
        }
    }

    generate()
    return results
}

// smoke test
print(permuteBruteForce([1, 2, 3]).count)   // 6
print(permuteBruteForce([]))                 // [[]]
print(permuteBruteForce([7]))                // [[7]]

Big-O: O(n^n) time — every one of the n^n length-n sequences over nums gets fully built before the Set check discards the ones with repeats. O(n) extra space per in-flight sequence.

🚀 Optimal

Track which indices are already used with a used array, and skip them before recursing — the search tree only ever contains the n! sequences that are actually valid permutations.

func permute(_ nums: [Int]) -> [[Int]] {
    var results: [[Int]] = []
    var path: [Int] = []
    var used = [Bool](repeating: false, count: nums.count)

    func backtrack() {
        if path.count == nums.count {
            results.append(path)
            return
        }

        for i in 0..<nums.count {
            if used[i] { continue }   // prune: this element is already in the current path

            used[i] = true
            path.append(nums[i])
            backtrack()
            path.removeLast()
            used[i] = false
        }
    }

    backtrack()
    return results
}

// smoke test — same cases as the brute force
print(permute([1, 2, 3]).count)   // 6
print(permute([]))                 // [[]]
print(permute([7]))                // [[7]]

Big-O: O(n · n!) time — n! permutations, each O(n) to copy when recorded, and O(1) extra work per recursive call thanks to the used check. O(n) extra space for used and path, not counting the output.

🔑 The Key Insight

n^n versus n! is not a small gap — for n = 10, that's ten billion sequences built and mostly discarded versus roughly 3.6 million kept. The brute force pays that price because it treats "which element is next" as an unconstrained choice from the full array every time, only noticing after the fact that it picked something twice. The used array turns that after-the-fact discovery into a before-the-fact skip: the instant an element is already spoken for, it's removed from consideration for the rest of that branch, so the recursion tree never grows the wasted branches in the first place.

🔗 Related Chapters

  • DFS and Backtracking — the same choose/recurse/un-choose skeleton, with a used tracker replacing the advancing start index used by Subsets and Combination Sum.
  • Arrays and Strings — path and used are both mutated in place throughout the search, appended/toggled on the way down and undone on the way back up.

🧸 Memory Sentence

Permutations is "pick any unused element next" — mark it used before you recurse, and un-mark it the instant you back out, so every branch only ever sees the elements that are actually still available.

✅ Check Your Understanding

  1. Why does permute loop over 0..<nums.count at every recursive call, instead of an advancing start index like subsets and combinationSum use?
  2. permute([]) returns [[]]. Walk through why backtrack() records an empty path immediately rather than looping forever or returning [].
  3. The brute force's Set(path).count == nums.count check only catches "all distinct," not "all of nums, each exactly once." Since nums has no duplicates and path.count == nums.count, why does "all distinct" end up being an equivalent condition here?

⬅️ Previous: Combination Sum · Next: Subsets II ➡️

Clone this wiki locally