M46.全排列

backtracking, https://leetcode.cn/problems/permutations/

思路：写一个回溯型的递归就行，非常简单，用时约15min

class Solution 
{
public:
    void backtrack(vector<int>& nums, vector<int>& current, vector<bool>& used, vector<vector<int>>& ans)
    {
        if (current.size() == nums.size())
        {
            ans.push_back(current);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (used[i]) continue;
            used[i] = true;
            current.push_back(nums[i]);
            backtrack(nums, current, used, ans);
            //回溯
            current.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) 
    {
        vector<vector<int>> ans;
        
        vector<int> current;
        vector<bool> used(nums.size(), false);
        backtrack(nums, current, used, ans);
        return ans;

    }
};

思路：经典全排列构造思路,那就是依次将每个数字放在开头,然后考虑后面的从而进行递归,时间复杂度是n!

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& nums, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(nums);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(nums[i], nums[first]);
            // 继续递归填下一个数
            backtrack(res, nums, first + 1, len);
            // 撤销操作
            swap(nums[i], nums[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};