Problem statement

Given an array nums of distinct integers, return all possible permutations, in lexicographic order (with the array's values sorted ascending first).

Example 1

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Constraints

• 1 <= nums.length <= 4
• -10 <= nums[i] <= 10
• All values distinct.

Hints for Permutations

1. Hint 1

   Backtracking with a 'used' array — pick each unused value in ascending order.

2. Hint 2

   Sorting first and always iterating candidates in order yields lexicographic output.

How to solve Permutations

A permutation uses every value exactly once, so unlike subsets there is no start index to move forward — any unused value may come next. Track which positions are already spent with a used array, and always scan candidates in sorted order so the output is lexicographic.

Approach

1. Sort nums ascending; the smallest permutation must come first.
2. Keep a used flag per index and a partial arrangement cur.
3. When cur holds all n values, record a copy — that is one complete permutation.
4. Otherwise loop over every index, skip the used ones, and for each unused index: mark it, append its value, recurse, then unmark and remove it.
5. Scanning indices in ascending order at every level keeps the answers sorted.

Why it works

Each recursion level fixes exactly one position of the arrangement, and the loop tries every value still available for it. That covers all n! orderings once each: two different runs must differ at the first level where they chose a different index. Because the values are sorted and each level walks them low to high, the permutations are produced in lexicographic order directly.

Complexity

• Time — O(n! · n)
• Space — O(n! · n)

Pitfalls

• Both parts of the state have to be undone after the recursive call — clear the used flag and pop the value. Undoing only one corrupts every later branch.
• There is no start index here; using one would generate combinations, not permutations.
• Store a copy at the base case, not the live working array.

Reference solution

Python

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    s = sorted(nums)
    out = []
    used = [False] * len(s)

    def go(cur):
        if len(cur) == len(s):
            out.append(cur[:])
            return
        for i in range(len(s)):
            if used[i]:
                continue
            used[i] = True
            cur.append(s[i])
            go(cur)
            cur.pop()
            used[i] = False

    go([])
    return out

Java

public static int[][] permute(int[] nums) {
    int[] s = nums.clone();
    Arrays.sort(s);
    List<int[]> out = new ArrayList<>();
    boolean[] used = new boolean[s.length];
    int[] cur = new int[s.length];
    goPermute(out, s, used, cur, 0);
    return out.toArray(new int[0][]);
}

private static void goPermute(List<int[]> out, int[] s, boolean[] used, int[] cur, int depth) {
    if (depth == s.length) {
        out.add(cur.clone());
        return;
    }
    for (int i = 0; i < s.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        cur[depth] = s[i];
        goPermute(out, s, used, cur, depth + 1);
        used[i] = false;
    }
}

C++

void goPermute(vector<vector<int>>& out, vector<int>& s, vector<bool>& used, vector<int>& cur) {
    if (cur.size() == s.size()) {
        out.push_back(cur);
        return;
    }
    for (size_t i = 0; i < s.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        cur.push_back(s[i]);
        goPermute(out, s, used, cur);
        cur.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    vector<vector<int>> out;
    vector<bool> used(s.size(), false);
    vector<int> cur;
    goPermute(out, s, used, cur);
    return out;
}

JavaScript

var permute = function(nums) {
    const s = nums.slice().sort(function(a, b) { return a - b; });
    const out = [];
    const used = new Array(s.length).fill(false);
    function go(cur) {
        if (cur.length === s.length) {
            out.push(cur.slice());
            return;
        }
        for (let i = 0; i < s.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            cur.push(s[i]);
            go(cur);
            cur.pop();
            used[i] = false;
        }
    }
    go([]);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium