Permutations

Practice Link

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Intuition#

This looks like Subsets at first glance — both are "generate all arrangements" backtracking problems — but the branching structure is different because order matters and every element must appear exactly once in every output. In Subsets, each element gets one independent include/exclude decision. Here, we instead fill positions one at a time, and at each position we choose which unused element goes there.

So the recursive shape is: build a sequence one slot at a time; at each slot, try every element that hasn't been placed yet; once all n slots are filled, one full permutation is complete. At recursion depth d, there are (n - d) remaining choices, giving n × (n-1) × ... × 1 = n! total permutations — each one taking O(n) to build/copy, so every approach below lands on O(n! × n) time no matter how the "which elements are still available" bookkeeping is implemented:

• Track availability explicitly with a used boolean array (approach 1) — simplest to read, costs O(n) extra space for the array.
• Track availability implicitly by swapping: partition nums in-place into an already-fixed prefix and a still-available suffix, swapping a candidate into the current position instead of maintaining a separate array (approach 2) — no extra visited array needed.
• Build permutations of longer prefixes from permutations of shorter ones: to place nums[i], take every permutation already built from the first i elements and insert nums[i] into every possible slot within each of them (approach 3) — no recursion at all, just iterative construction.
• Let the standard library do the bookkeeping: sort once, then repeatedly call next_permutation until it wraps back around (approach 4) — shortest code, leans on <algorithm>.

Approach 1: Backtracking with a used array#

class Solution {
public:
    void permuteUtil(vector<int>& nums, vector<int>& curr, vector<bool>& used, vector<vector<int>>& ans) {
        if (curr.size() == nums.size()) {
            ans.push_back(curr);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            used[i] = true;
            curr.push_back(nums[i]);
            permuteUtil(nums, curr, used, ans);
            curr.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> curr;
        vector<bool> used(nums.size(), false);
        permuteUtil(nums, curr, used, ans);
        return ans;
    }
};

Time Complexity: O(n! × n) — n! permutations, each built and copied at cost O(n).

Space Complexity: O(n! × n) for the output, plus O(n) for the used array and O(n) recursion stack depth.

Approach 2: Backtracking via in-place swapping#

Instead of a separate used array, treat nums[0..idx-1] as the fixed prefix and nums[idx..n-1] as the pool of still-available elements. Swap each candidate into position idx, recurse, then swap back to restore the array before trying the next candidate.

class Solution {
public:
    void permuteUtil(vector<int>& nums, int idx, vector<vector<int>>& ans) {
        if (idx == nums.size()) {
            ans.push_back(nums);
            return;
        }
        for (int i = idx; i < nums.size(); i++) {
            swap(nums[idx], nums[i]);
            permuteUtil(nums, idx + 1, ans);
            swap(nums[idx], nums[i]);   // backtrack: restore original order
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        permuteUtil(nums, 0, ans);
        return ans;
    }
};

Time Complexity: O(n! × n) — same permutation count and copy cost as approach 1.

Space Complexity: O(n! × n) for the output, plus O(n) recursion stack depth (no extra visited array).

Approach 3: Iterative (insert into every position)#

Start with just the empty permutation. For each new number, take every permutation built so far and generate one new permutation per insertion point — this is what grows the count from (k-1)! to k! at each step.

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans = {{}};
        for (int num : nums) {
            vector<vector<int>> next;
            for (auto& perm : ans) {
                for (int pos = 0; pos <= (int)perm.size(); pos++) {
                    vector<int> newPerm = perm;
                    newPerm.insert(newPerm.begin() + pos, num);
                    next.push_back(newPerm);
                }
            }
            ans = next;
        }
        return ans;
    }
};

Time Complexity: O(n! × n) — at the point where k numbers have been processed there are k! permutations, each of length k, so the copy/insert cost per stage is k! × k; summed over all stages this is dominated by the final stage, O(n! × n).

Space Complexity: O(n! × n) for the output (the intermediate next list is the same order of size at the final stage).

Approach 4: std::next_permutation#

Since nums has distinct elements, sorting it first gives the lexicographically smallest permutation, and repeatedly calling next_permutation visits every one of the n! permutations in order, wrapping back to sorted order (returning false) only after all have been produced.

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        do {
            ans.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));
        return ans;
    }
};

Time Complexity: O(n! × n) — n! iterations of the do...while, each doing an O(n) push_back copy (next_permutation itself is O(n) worst case, amortized less).

Space Complexity: O(n! × n) for the output; O(1) extra space beyond that (no recursion, no separate bookkeeping structure).