Permutations

PracticeNeetCode ↗LeetCode ↗

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

Example

Key Pointers

• Unlike subsets, order matters — every unused number is a valid next choice at every position, not just numbers after some index.
• Track which numbers are already placed with a used boolean array instead of slicing the remaining list, to avoid rebuilding a list at every step.
• A full permutation is complete exactly when path's length equals nums's length.

Step-by-Step Analysis

1. Create a used array of False, length n.
2. Define backtrack(): if len(path) == len(nums), record a copy of path and return.
3. Loop over every index i in nums: skip it if used[i] is True.
4. Otherwise mark used[i] = True, append nums[i] to path, recurse, then undo both (pop path, used[i] = False).
5. Call backtrack() and return the result.

Complexity

Time: O(n · n!) — Space: O(n) recursion depth

Code

def permute(nums: list[int]) -> list[list[int]]:
    result = []
    path = []
    used = [False] * len(nums)

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

    backtrack()
    return result

Code Explanation

How the solution above works, piece by piece.

1. used[i] marks which numbers are already in path.
2. When path holds all n numbers, it's a complete permutation: save a copy.
3. Otherwise try every unused number at this position (the loop starts at 0 every time, unlike subsets).
4. Mark it used, recurse, then un-mark it and pop: this backtracking restores the state for the next choice.
5. n! permutations, each copied in O(n): O(n · n!) time.

Visual Walkthrough

The recursion tree for nums = [1, 2, 3]:

Video Explanation

NeetCode — Backtracking, LeetCode 46