Permutations

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given a list of distinct integers, return every possible ordering of them. The orderings can be returned in any order. With n numbers there are n! of them, so n is small (at most about 8).

    This is the textbook backtracking problem. Once you can write it cleanly, Subsets, Combination Sum and N-Queens are small changes to the same template. Original problem: LeetCode 46.

    Example

    Three numbers have 3 × 2 × 1 = 6 orderings.
    Three numbers have 3 × 2 × 1 = 6 orderings.
    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]]

    Constraints (assumed)

    • 1 ≤ n ≤ 8.
    • All numbers are distinct, −10 ≤ value ≤ 10.

    What this question tests

    • Writing the choose → recurse → un-choose backtracking template without mistakes.
    • Knowing what state to keep (the path and which numbers are used) and how to restore it.
    • Reasoning about output-sized complexity: you can't beat n! when you must print n! answers.

    Questions to ask first

    1. Are the numbers distinct? If not, duplicates need extra handling (see Variants).
    2. Does the output order matter? (Here: no.)
    3. How large is n? n! grows fast: 10! is already 3.6 million lists.
    4. Do you want all of them, or just the next one / the k-th one? Those are different problems with better answers.