Permutations

Problem

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

Examples

Example 1:

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]

Example 2:

Input: nums = [7]

Output: [[7]]

Constraints

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10

You should aim for a solution with O(n * n!) time and O(n) space, where n is the size of the input array.

Solution

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> res;
        std::unordered_set<int> res_set;
        std::function<void(int)> dfs;
        dfs = [&](int idx) {
            if (idx == nums.size()) {
                result.push_back(res);
                return;
            }
            for (const auto &num : nums) {
                if (res_set.contains(num)) { continue; }
                res.push_back(num);
                res_set.insert(num);
                dfs(idx + 1);
                res.pop_back();
                res_set.erase(num);
            }
        };
        dfs(0);
        return result;
    }
};