← Algorithmic Patterns
mediumBacktracking

Permutations

Generate all orderings of distinct integers.

LeetCode ↗

Work through the cases

3 examples

Input notation

Distinct integers separated by spaces; at most 8 values.

Expected result

One space-separated permutation per line in lexicographic order.
Case 1

Input

1 2

Expected output

1 2
2 1
Case 2

Input

3

Expected output

3
Case 3

Input

-1 0

Expected output

-1 0
0 -1

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is a language builtin or nested loops. n ≤ 6 so n! fits, but n is not fixed — we cannot hard-code loop depth. Generating every permutation means “pick an unused number for this position”. Reusing a number breaks the permutation, so we must mark. DFS fills index i: try each unused value, place it, recurse, then undo. n is tiny; O(n × n!) matches the output size.

We design a function dfs(i) to represent that the first i positions have been filled, and now we need to fill the i+1 position. We enumerate all possible numbers, if this number has not been filled, we fill in this number, and then continue to fill the next position, until all positions are filled.

The time complexity is O(n × n!), where n is the length of the array. There are n! permutations in total, and each permutation takes O(n) time to construct.

Similar problems:

- 47. Permutations II

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> t = new ArrayList<>();
    private boolean[] vis;
    private int[] nums;

    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        vis = new boolean[nums.length];
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(t));
            return;
        }
        for (int j = 0; j < nums.length; ++j) {
            if (!vis[j]) {
                vis[j] = true;
                t.add(nums[j]);
                dfs(i + 1);
                t.remove(t.size() - 1);
                vis[j] = false;
            }
        }
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.