46. Permutations

class Solution {
private:
    vector<vector<int>> res;
public:
    vector<vector<int>> permute(vector<int>& nums)
    {
        backtracking(nums, 0);
        return res;
    }

    void backtracking(vector<int>& nums, int start)
    {
        if (start == nums.size())
        {
            res.push_back(nums); return;
        }

        for (int i = start; i < nums.size(); ++i)
        {
            swap(nums[i], nums[start]);
            backtracking(nums, start + 1);
            swap(nums[i], nums[start]);
        }
    }
};

• T: $O(n \cdot n!)$
• S: $O(n)$