LeetCode 47 全排列II

47.全排列II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

双hash+回溯递归

本题在46.全排列问题的基础之上发生了改变，主要的不同之处在于：给定的序列中包含重复的元素，那么在全排列的过程中就会导致重复的结果，例如 nums=[1,1,2] 完全按照排列问题进行处理将会出现重复结果： [1,2,1] 和 [1,1,2] ，那么在于全排列问题的基础上此处的重点就在于处理重复的结果。

那么基本思路还是：递归实现，每一层选取一个元素作为排列中的第 cur 个元素，当 cur=nums.size() 选取结束，将排列加入到结果集中。

此处采取双hash的方式进行处理，创建两个hash表：

1. used[8] 是一个全局变量，记录的是整个序列中那些位置的的元素已经使用了 used[i]=true 代表 nums[i] 处的元素已经在前层使用了。那么在某层选取 nums[i] 后需要对 used[i] 进行标记，在递归返回后需要进行回溯，取消标记（ nums 的最大长度为8，定长数组即可）
2. curUsed[21] 是递归函数中的局部变量，记录的是在当前层中那些元素值已经使用过了， curUed[i]=true 表示在当前层元素值 i 已经使用过了，假设当前的递归层数为第 j 层，那么表示在排列的第 j 个位置已经使用过元素 i ，那么在当前层的后续选择中遇到元素 i 就需要进行跳过

代码实现：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    bool used[8]={false}; // 记录那些位置的元素被使用
    void DFS(vector<int>& nums,int cur){
        if(cur==nums.size()){
            res.push_back(tmp);
        }
        int curUsed[21]={false}; // 记录当前层那些元素值被使用了
        for(int i=0;i<nums.size();i++){
            if(!used[i]&&!curUsed[nums[i]+10]){ // 在前层和当前层都没有使用过
                used[i]=true; // 标记使用
                tmp.push_back(nums[i]);
                curUsed[nums[i]+10]=true;
                DFS(nums,cur+1);
                tmp.pop_back();
                used[i]=false;
            }
        }   
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        DFS(nums,0);
        return res;
    }
};

单hash削减空间复杂度

将数组 nums 排序，使用单个hash进行记录。使用一个hash vis 记录 nums 数组中的第i个元素是否被使用。在第i层进行元素的选取时，若是当前元素和前一个元素相等，并且上一个元素在当前层没有被选择，那么就不选择该元素。也就是对于多个连续的重复元素，在第i层中要对齐进行选取，仅仅选取一次，那么这一次就是选取多个连续重复元素中的第一个元素。当然对于 vis[i]==true 的情形，肯定是不能进行选取了。

if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
    continue;
}

整体代码实现：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    bool used[8]={false}; // 记录那些位置的元素被使用
    void DFS(vector<int>& nums,int cur){
        if(cur==nums.size()){
            res.push_back(tmp);
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]||(i>0&&nums[i]==nums[i-1]&&!used[i-1])){
                continue;
            }
            used[i]=true; // 标记使用
            tmp.push_back(nums[i]);
            DFS(nums,cur+1);
            tmp.pop_back();
            used[i]=false;        
        }   
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        DFS(nums,0);
        return res;
    }
};