DSA

Permutations

4 approaches incl. Backtracking with a `used` a…, Backtracking via in-place sw…, Iterative (insert into every…, and more. Optimal — Time O(n), Space O(1).

August 8, 2026
PatternBacktrackingOptimalO(n) time · O(1) space
Solve on LeetCode
Key insighttry it first, then reveal

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…

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#

cpp
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.

cpp
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.

cpp
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.

cpp
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).