Permutations

MediumBacktracking🧩 Backtracking LeetCode #46 ↗Updated Oct 30, 2026

Problem

Given an array nums of distinct integers, return every possible ordering (permutation) of its elements. The orderings may be returned in any order.

Input[1,2,3]Output[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Input[0,1]Output[[0,1],[1,0]]

Input[1]Output[[1]]

1 ≤ n ≤ 6 · -10 ≤ nums[i] ≤ 10 · all values distinct

Try it yourself

Java

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A permutation is a sequence of n choices, each picking an element not used yet. Track usage with a boolean[] used, recurse, then undo the choice — the decision tree has exactly n! leaves.

PatternBacktracking

Instinct Return ALL combinations, permutations, partitions or placements - or ask if any arrangement works - build a candidate step by step and undo each choice.

Memory hack Choose, explore, un-choose - walk the decision tree and snip a branch the moment it can no longer succeed.

Open the Backtracking guide →

Approaches

Brute ForceAll nⁿ Index Sequences, Then Filter

Time O(n · nⁿ)Space O(n) extra

Fill each of the n slots with any index (repeats allowed), giving nⁿ sequences; keep only those where all indices are distinct. Correct, but most sequences are thrown away (e.g. 46,656 vs 720 for n=6).

Java

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    generate(nums, new int[nums.length], 0, res);
    return res;
}
private void generate(int[] nums, int[] idx, int pos, List<List<Integer>> res) {
    int n = nums.length;
    if (pos == n) {
        boolean[] seen = new boolean[n];
        List<Integer> perm = new ArrayList<>();
        for (int i : idx) {
            if (seen[i]) return; // repeated index -> not a permutation
            seen[i] = true;
            perm.add(nums[i]);
        }
        res.add(perm);
        return;
    }
    for (int i = 0; i < n; i++) {
        idx[pos] = i;
        generate(nums, idx, pos + 1, res);
    }
}

Simple generate-and-test, but nⁿ grows far faster than n!.

BetterIterative Insertion

Time O(n · n!)Space O(n!) extra

Start from [[]]. For each new number, insert it into every gap (size+1 positions) of every permutation built so far. After k numbers there are k! lists, all distinct because the inserted positions differ.

Java

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    res.add(new ArrayList<>());
    for (int num : nums) {
        List<List<Integer>> next = new ArrayList<>();
        for (List<Integer> perm : res) {
            for (int i = 0; i <= perm.size(); i++) {
                List<Integer> np = new ArrayList<>(perm);
                np.add(i, num); // insert into gap i
                next.add(np);
            }
        }
        res = next;
    }
    return res;
}

No wasted sequences and no recursion, but copies whole intermediate levels.

OptimalBacktracking with `used[]`

Time O(n · n!)Space O(n) extra

Build one path. At each depth, try every index not yet used, mark it, recurse, then unmark and pop. Only valid prefixes are ever extended, so there are exactly n! leaves, each copied in O(n).

Java

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, new ArrayList<>(), new boolean[nums.length], res);
    return res;
}
private void backtrack(int[] nums, List<Integer> path, boolean[] used,
                       List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, path, used, res);
        path.remove(path.size() - 1); // undo
        used[i] = false;
    }
}

Output-optimal with O(n) extra space (excluding output) — the standard template.

Pro tip

For Permutations II (duplicates), sort first and skip nums[i] when it equals nums[i-1] and !used[i-1].

At a glance

Level	Approach	Time	Space
Brute Force	All nⁿ Index Sequences, Then Filter	`O(n · nⁿ)`	`O(n) extra`
Better	Iterative Insertion	`O(n · n!)`	`O(n!) extra`
Optimal	Backtracking with `used[]`	`O(n · n!)`	`O(n) extra`

Common pitfalls

Adding path itself instead of a copy — every result ends up empty.
Forgetting to reset used[i] = false after recursing.
path.remove(x) with an Integer removes by value; pop by index.

Interview tips

Draw the decision tree: n choices, then n-1, ... → n! leaves.
State complexity as O(n · n!) — the copy at each leaf costs O(n).
Mention the swap-in-place variant, which avoids the used array.

Pattern

Backtracking with a used-set → enumerate orderings where each element appears exactly once.

My notes saved in this browser