# [46\. Permutations](https://leetcode.com/problems/permutations/)

:::spoiler Hint

class Solution {
private:
    // Vector to store all permutations
public:
    vector<vector<int>> permute(vector<int>& nums)
    {
        // Start backtracking from index 0
        // Return the result
    }

    // Helper function to perform backtracking
    void backtracking(vector<int>& nums, int start)
    {
        // If the current permutation is complete
        if ()
        {
            // Add the current permutation to the result
        }

        // Iterate over the range starting from 'start' to the end of the vector
        for ()
        {
            // Swap the current element with the element at 'start'
            // Recur to generate permutations with the next element
            // Backtrack by swapping the elements back to their original positions
        }
    }
};

:::

:::spoiler Solution

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)$
:::