Permutations

MediumBacktracking

Return all possible orderings of an array of distinct integers.

Constraints

1 <= nums.length <= 6
All integers are unique

Backtracking with a used set

Time O(n * n!)Space O(n) recursion depth

Build a permutation position by position, marking values as used so each appears once, and unmarking on the way back to explore other branches.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> cur;
    vector<bool> used(nums.size(), false);
    function<void()> bt = [&]() {
        if (cur.size() == nums.size()) { res.push_back(cur); return; }
        for (int i = 0; i < (int)nums.size(); i++) {
            if (used[i]) continue;
            used[i] = true; cur.push_back(nums[i]);
            bt();
            cur.pop_back(); used[i] = false;
        }
    };
    bt();
    return res;
}