Permutations · All Orderings

Every ordering of the elements. At each level you pick any element not used yet, so the branching factor shrinks n, n-1, n-2, …, giving n! leaves.

Concept

Pick any unused

Keep a used[] flag per element. At each recursion level, loop over all elements and branch into every one that's still free. Mark it used, recurse, then unmark.

When the path length hits n, you've built one full permutation.

Why n!

Level 0: n choices
Level 1: n-1 remaining
… down to 1 choice at the last
n × (n-1) × … × 1 = n! permutations

Interactive

Build every ordering

Unvisited Active Permutation found Backtracked

Elements

current path:

slowfast

Step 0

Nodes explored

Permutations

Expected n!

–

Depth

Implementation

C++

void dfs(vector<int>& nums, vector<bool>& used,
         vector<int>& path, vector<vector<int>>& out) {
    if (path.size() == nums.size()) {   // full permutation
        out.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;         // skip already-placed
        used[i] = true;               // CHOOSE
        path.push_back(nums[i]);
        dfs(nums, used, path, out);    // EXPLORE
        path.pop_back();               // UNCHOOSE
        used[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> out;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    dfs(nums, used, path, out);
    return out;                        // n! permutations
}

Complexity

Time

O(n! · n)

n! permutations, each length n to copy into the output.

Space

O(n)

Recursion depth, path, and the used[] flag array.

Output

Factorial growth, 3! = 6, 4! = 24, 5! = 120.

Notes

used[] vs swapping: the flag approach keeps input order readable; the in-place swap version saves the array but scrambles order. Both hit n!.
For duplicates (LC 47), sort and skip nums[i]==nums[i-1] && !used[i-1] to avoid identical permutations.
Branching factor shrinks each level as choices get used up, that's the visual funnel in the tree.
The path here is recorded only at leaves (length n); prefixes aren't valid permutations.
Next-permutation (LC 31) is the O(n) iterative cousin when you only need the next ordering, not all.