Permutations

Problem

Given an array nums of distinct integers, return all possible permutations of its elements. A permutation is an arrangement that uses every element exactly once; two permutations differ if the elements appear in a different order.

You may return the permutations in any order, but each of the n! distinct orderings must appear exactly once.

Examples

• Input: nums = [1, 2, 3] → Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] All 3! = 6 orderings of three distinct numbers.
• Input: nums = [0, 1] → Output: [[0,1], [1,0]] The two orderings of a pair.
• Input: nums = [7] → Output: [[7]] A single element has exactly one permutation.

Constraints

• 1 <= nums.length <= 6.
• -10 <= nums[i] <= 10.
• All integers in nums are distinct.

With n <= 6, the output has at most 6! = 720 permutations — small, but the enumeration itself is inherently factorial.

Think about it first

TL;DR

Backtrack, filling one position at a time using a used marker (or in-place swaps) — O(n · n!) time, O(n) recursion depth.

Approach 1 — Backtracking with a used array

The intuition: grow a partial permutation path. At each level, scan all elements and, for any element not yet used, place it, mark it used, recurse, then unmark and remove it. When path has all n elements, snapshot it into the result.

from typing import List

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

        def backtrack() -> None:
            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

Walkthrough on nums = [1, 2, 3]:

• Place 1 → path [1]. Place 2 → [1,2]. Place 3 → [1,2,3] (length 3, record). Undo to [1,2], no more choices; undo to [1]. Place 3 → [1,3], then 2 → [1,3,2] (record).
• Undo back to [], place 2 → branch yields [2,1,3] and [2,3,1].
• Undo, place 3 → branch yields [3,1,2] and [3,2,1].

Result: all 6 permutations.

Complexity: O(n · n!) time — there are n! leaves and copying each completed permutation costs O(n) — and O(n) auxiliary space for path and used (excluding output).

Approach 2 — In-place swapping (no auxiliary used)

The insight: you can generate permutations by fixing one position at a time directly inside the array. At index first, swap each candidate nums[i] (for i >= first) into position first, recurse on first + 1, then swap back to restore the array. This avoids the separate used array and the growing path — the array itself carries the state.

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result: List[List[int]] = []

        def backtrack(first: int) -> None:
            if first == n:
                result.append(nums[:])
                return
            for i in range(first, n):
                nums[first], nums[i] = nums[i], nums[first]
                backtrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first]

        backtrack(0)
        return result

Walkthrough on nums = [1, 2, 3] at first = 0:

• i = 0: no-op swap, recurse with [1,2,3] → fixes 1, produces [1,2,3] and [1,3,2].
• i = 1: swap positions 0 and 1 → [2,1,3], recurse → produces [2,1,3] and [2,3,1], then swap back to [1,2,3].
• i = 2: swap positions 0 and 2 → [3,2,1], recurse → produces [3,2,1] and [3,1,2], swap back.

Same 6 permutations, generated in a different order (order is unconstrained by the problem).

Complexity: O(n · n!) time, O(n) recursion-stack space — and no extra used/path buffers, so slightly lower constant-factor memory than Approach 1.

Common pitfalls

• Storing path by reference. result.append(path) keeps a live alias that mutates; use path[:] (or nums[:]) to record a snapshot.
• Forgetting to undo. Skipping path.pop() / used[i] = False, or the reverse swap, corrupts sibling branches and yields duplicates or missing permutations.
• Swapping back with the wrong indices. In the in-place version, the restore swap must mirror the exact same first/i pair, or the array drifts out of its original state.
• Assuming duplicates are handled. This problem guarantees distinct inputs; the plain version would emit repeats on duplicate values — that variant (Permutations II) needs an extra sort-and-skip guard.

Pattern takeaway

Permutation generation is the archetype of “choose an item for each position, recurse, undo.” Whether you track availability with a used array or by swapping in place, the invariant is the same: every choice you make must be exactly reversed on the way back up so each branch starts from a clean state.