46. Permutations (Medium)

Problem

Given an array nums of distinct integers, return all possible permutations. You may return them in any order.

Example

• nums = [1, 2, 3] → [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
• nums = [0, 1] → [[0, 1], [1, 0]]

LeetCode 46 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, itertools.permutations

Python’s standard library does this directly.

from itertools import permutations

def permute(nums):
    return [list(p) for p in permutations(nums)]  # L1: O(n · n!) total output

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (generate + convert)	$O(n)$ per permutation	n!	$O(n · n!)$ ← dominates

Complexity

• Time: $O(n · n!)$, driven by L1 generating and copying n! permutations each of length n.
• Space: $O(n · n!)$ output.

Production-correct; usually rejected in interviews that want the algorithm.

Swift

final class Solution {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func permute(_ nums: [Int]) -> [[Int]] {
        if nums.isEmpty { return [[]] }; var result: [[Int]] = []
        for value in nums { let remaining = nums.filter { $0 != value }; for suffix in permute(remaining) { result.append([value] + suffix) } }
        return normalized(result)
    }
}

Approach 2: Backtracking with a used array

Track which indices have been consumed; at each recursion, try every unused index.

Python

def permute(nums):
    result = []
    n = len(nums)
    used = [False] * n
    path = []

    def backtrack():
        if len(path) == n:
            result.append(path[:])      # L1: O(n) copy at leaf
            return
        for i in range(n):
            if used[i]:
                continue                # L2: O(1) skip used
            used[i] = True             # L3: O(1) mark used
            path.append(nums[i])        # L4: O(1) push
            backtrack()                 # L5: recurse
            path.pop()                 # L6: O(1) pop
            used[i] = False            # L7: O(1) unmark

    backtrack()
    return result

TypeScript

function permute(nums: number[]): number[][] {
    const result: number[][] = [];
    const n = nums.length;
    const used: boolean[] = new Array(n).fill(false);
    const path: number[] = [];

    function backtrack(): void {
        if (path.length === n) {
            result.push([...path]);      // L1: O(n) copy at leaf
            return;
        }
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;       // L2: O(1) skip used
            used[i] = true;             // L3: O(1) mark used
            path.push(nums[i]);          // L4: O(1) push
            backtrack();                 // L5: recurse
            path.pop();                 // L6: O(1) pop
            used[i] = false;            // L7: O(1) unmark
        }
    }

    backtrack();
    return result;
}

Go

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

    var backtrack func()
    backtrack = func() {
        if len(path) == n {
            cp := make([]int, len(path))
            copy(cp, path)
            result = append(result, cp)  // L1: O(n) copy at leaf
            return
        }
        for i := 0; i < n; i++ {
            if used[i] {
                continue                 // L2: O(1) skip used
            }
            used[i] = true               // L3: O(1) mark used
            path = append(path, nums[i]) // L4: O(1) push
            backtrack()                  // L5: recurse
            path = path[:len(path)-1]    // L6: O(1) pop
            used[i] = false              // L7: O(1) unmark
        }
    }

    backtrack()
    return result
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (copy)	$O(n)$	n!	$O(n · n!)$
L2 (skip)	$O(1)$	n per level	$O(n · n!)$
L5 (recurse)	$O(1)$ dispatch	n · n! nodes	$O(n · n!)$ ← dominates (all lines tie)

The recursion tree has n! leaves, each at depth n, giving $O(n · n!)$ total node visits.

Complexity

• Time: $O(n · n!)$, driven by L5 traversing the full permutation tree.
• Space: $O(n)$ recursion + output.

The clearest expression of the backtracking template for permutations.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func permute(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = [], used = Array(repeating: false, count: nums.count)
        func search(_ current: [Int]) { if current.count == nums.count { result.append(current); return }; for index in nums.indices where !used[index] { used[index] = true; search(current + [nums[index]]); used[index] = false } }
        search([]); return normalized(result)
    }
}

Approach 3: In-place swap (no auxiliary used)

Swap the current position with every other position; recurse on the tail. Undo the swap on the way back up.

Python

def permute(nums):
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])          # L1: O(n) copy
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]   # L2: O(1) swap
            backtrack(start + 1)                          # L3: recurse
            nums[start], nums[i] = nums[i], nums[start]   # L4: O(1) undo swap

    backtrack(0)
    return result

TypeScript

function permute(nums: number[]): number[][] {
    const result: number[][] = [];
    const arr = [...nums];

    function backtrack(start: number): void {
        if (start === arr.length) {
            result.push([...arr]);              // L1: O(n) copy
            return;
        }
        for (let i = start; i < arr.length; i++) {
            [arr[start], arr[i]] = [arr[i], arr[start]];  // L2: O(1) swap
            backtrack(start + 1);                          // L3: recurse
            [arr[start], arr[i]] = [arr[i], arr[start]];  // L4: O(1) undo swap
        }
    }

    backtrack(0);
    return result;
}

Go

func permute(nums []int) [][]int {
    result := [][]int{}
    arr := make([]int, len(nums))
    copy(arr, nums)

    var backtrack func(start int)
    backtrack = func(start int) {
        if start == len(arr) {
            cp := make([]int, len(arr))
            copy(cp, arr)
            result = append(result, cp)              // L1: O(n) copy
            return
        }
        for i := start; i < len(arr); i++ {
            arr[start], arr[i] = arr[i], arr[start] // L2: O(1) swap
            backtrack(start + 1)                     // L3: recurse
            arr[start], arr[i] = arr[i], arr[start] // L4: O(1) undo swap
        }
    }

    backtrack(0)
    return result
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (copy)	$O(n)$	n!	$O(n · n!)$
L2/L4 (swap + undo)	$O(1)$	n · n!	$O(n · n!)$
L3 (recurse)	$O(1)$ dispatch	n · n! nodes	$O(n · n!)$ ← dominates (all lines tie)

Complexity

• Time: $O(n · n!)$.
• Space: $O(n)$ recursion.

Saves the used array. Slightly less readable; mutates input.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func permute(_ nums: [Int]) -> [[Int]] {
        var values = nums, result: [[Int]] = []
        func search(_ start: Int) { if start == values.count { result.append(values); return }; for index in start..<values.count { values.swapAt(start, index); search(start + 1); values.swapAt(start, index) } }
        search(0); return normalized(result)
    }
}

Summary

Approach	Time	Space
itertools.permutations	$O(n · n!)$	$O(n · n!)$
Backtracking + used	$O(n · n!)$	$O(n)$ recursion
In-place swap	$O(n · n!)$	$O(n)$ recursion

All three are optimal in Big-O (output is itself $O(n · n!)$). Backtracking with used is the cleanest template; extends directly to Permutations II (duplicates allowed).

Test cases

Python

def permute(nums):
    result = []
    n = len(nums)
    used = [False] * n
    path = []
    def backtrack():
        if len(path) == n:
            result.append(path[:])
            return
        for i in range(n):
            if used[i]: continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False
    backtrack()
    return result

def _run_tests():
    r = permute([1, 2, 3])
    assert len(r) == 6
    assert sorted(map(tuple, r)) == sorted([
        (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)])
    r2 = permute([0, 1])
    assert sorted(map(tuple, r2)) == [(0,1),(1,0)]
    # single element
    assert permute([1]) == [[1]]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function permute(nums: number[]): number[][] {
    const result: number[][] = [];
    const n = nums.length;
    const used: boolean[] = new Array(n).fill(false);
    const path: number[] = [];
    function backtrack(): void {
        if (path.length === n) { result.push([...path]); return; }
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.push(nums[i]);
            backtrack();
            path.pop();
            used[i] = false;
        }
    }
    backtrack();
    return result;
}

const norm = (arr: number[][]): string =>
    JSON.stringify(arr.map(a => [...a]).sort((a, b) => JSON.stringify(a) < JSON.stringify(b) ? -1 : 1));

const r = permute([1, 2, 3]);
console.assert(r.length === 6);
console.assert(norm(r) === norm([[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]));
console.assert(norm(permute([0,1])) === norm([[0,1],[1,0]]));
console.assert(JSON.stringify(permute([1])) === JSON.stringify([[1]]));
console.log("all tests pass");

Go

func permute(nums []int) [][]int {
    result := [][]int{}
    n := len(nums)
    used := make([]bool, n)
    path := []int{}
    var backtrack func()
    backtrack = func() {
        if len(path) == n {
            cp := make([]int, len(path))
            copy(cp, path)
            result = append(result, cp)
            return
        }
        for i := 0; i < n; i++ {
            if used[i] { continue }
            used[i] = true
            path = append(path, nums[i])
            backtrack()
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    backtrack()
    return result
}

Related data structures

• Arrays, input; used marker array

Related concepts

• Backtracking, search-tree tactics for exploring choices, undoing state, and pruning invalid branches.
• Permutations, ordering tactics for generating arrangements where the same items in a different order are different answers.