LeetCode 46 全排列

46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

hash+回溯递归

排列问题和组合问题类似，都是从数组中选取全部的元素，但是排列问题相较于组合对顺序敏感，也就是对于 [1,2] 和 [2,1] 是两个不同的结果，因此在每一层进行元素的选取时，都从 i=0 开始选取，但是需要避免选择前层已经选取过的元素，使用一个hash去记录前层那些元素已经选取过了。在题设中，已知： ，因此只需要个长度为21的bool数组作为hash即可。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    bool used[21]={false};
    void DFS(vector<int>& nums){
        if(tmp.size()==nums.size()){
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(!used[nums[i]+10]){
                tmp.push_back(nums[i]);
                used[nums[i]+10]=true;
                DFS(nums);
                tmp.pop_back();
                used[nums[i]+10]=false;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        DFS(nums);
        return res;
    }
};

使用交换操作取代hash

在上述思路的基础上：

使用hash将会导致空间复杂度的上升，那么此处尝试利用原数组和下标的方式对已经加入排列的数据进行记录：使用 first 记录当前填充的位置，那么对于数组 nums 进行划分，使得从 [0,first-1] 处的元素都是选中的，从 [first,n-1] 处的元素都是未选择的。当在 [first,n-1] 范围内选择当前层的元素时，将这个元素和 first 处的元素进行交换，然后 first+1 向下递归，在递归返回后，回溯，将先前的元素与 first 处的元素换回来。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    void DFS(vector<int>& nums,int first){
        if(first==nums.size()){
            res.push_back(tmp);
            return;
        }
        for(int i=first;i<nums.size();i++){
            tmp.push_back(nums[i]);
            swap(nums[i],nums[first]);
            DFS(nums,first+1);
            swap(nums[i],nums[first]);
            tmp.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        DFS(nums,0);
        return res;
    }
};

此处还可以进一步简化，将中间数组 tmp 转化为递归函数的参数进行传递，（实际上传递数组 nums 即可）。

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