LeetCode 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解析：
此题是上一个题目LeetCode 46. Permutations的后续，只不过上一个题目给出的集合中没有重复项，当前题目中有重复数字，并且要求返回的结果不重复。
因此在进行dfs递归时需要判断避免重复的生成，对候选集合进行排序，对每一个元素判断当前元素与前一个元素是否相等，如果相等，前面的数必须已经使用了，即对应的used中的值为1，当前的数字才能使用，否则需要跳过，这样就不会产生重复排列了。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> ans;
        int num_lens;
        num_lens = nums.size();
        sort(nums.begin(), nums.end());
        if(nums.empty())
            return result;
        vector<bool> used(num_lens, false);
        dfs(nums, used, result, ans);
        return result;       
    }
    void dfs(vector<int> &nums, vector<bool> &used, vector<vector<int>> &result, vector<int> &ans)
    {
        if(ans.size() == nums.size())
            result.push_back(ans);
        else if(ans.size() > nums.size())
            return;
        else
        {
            for(int i=0; i < nums.size(); i++)
            {
                if(!used[i])
                {
                    if(i>0 && nums[i-1]==nums[i] && !used[i-1])
                        continue;
                    used[i] = true;
                    ans.push_back(nums[i]);
                    dfs(nums, used, result, ans);
                    ans.pop_back();
                    used[i] = false;
                }
            }
        }
    }
    
};

比较有意思的是：避免重复的这段代码
if(i>0 && nums[i-1]==nums[i] && !used[i-1]) continue; 和
if(i>0 && nums[i-1]==nums[i] && used[i-1]) continue;
竟然运行都可以通过，但是前一个时间更短，也是更推荐的。


由此可看，if(i>0 && nums[i-1]==nums[i] && !used[i-1])这种写法开始更节省时间的。具体分析一下：
我们以数组[1,2,2′]为例。
a.对于if(i>0 && nums[i-1]==nums[i] && used[i-1]) continue;的情况：
level 1，加入1，此时结果数组为[1]，
递归进入level2，从i=0开始遍历:
i=0时,nums[0]=1，此时used为True;
i=1时,nums[1]=2，used为False，加入，此时结果数组为[1,2]，
进入level3：
i=0时used为True；
i=1时used为True；
i=2时，nums[2]==nums[1]并且used[1]=true，所以此种情况不符合题意，跳过。
回溯到level2，之前遍历下标为1，现在继续遍历下标2，结果集为[1,2′]。
进入level3：
i=0时，used[0]=true;
i=1时，used[1]=fase;加入，得到结果为[1,2′,2]
对于结果集中第一个元素为2时，我们分析不符合题意的情况。
当结果集为[2,1]时，进入level3
i=0时，used[0]=true；i=1时，used[1]=true。i=2时，nums[2]==nums[1]并且used[1]==true，此时continue跳过。
不符合题意的两种情况中，在第level3进行判断时，前面的递归已经走到level2了，并且level2已经遍历完成，最后一步才发现不合适。
b.对于if(i>0 && nums[i-1]==nums[i] && !used[i-1]) continue;情况
我们只分析不符合题意的情况，
在level1级别，前面的1,2已经遍历完成，遍历到i=2时，结果集为空，此时判断是否要加入2’到结果集中，根据条件nums[2]==nums[1]&&used[1]==false，此种情况不满足，跳过，所以以2’开头的都已经跳过，后续不再进行遍历，这样就减少了遍历的次数，时间也会更短。

这里详细介绍一下剪枝逻辑中的!used[i-1]的判断逻辑。

为了方便研究，依然把相同的元素用上标’以示区别。

假设输入为nums = [1,2,2′]，标准的全排列算法会得出如下答案：

[
    [1,2,2′],[1,2′,2],
    [2,1,2′],[2,2′,1],
    [2′,1,2],[2′,2,1]
]

显然，这个结果存在重复，比如[1,2,2′]和[1,2′,2]应该只被算作同一个排列，但被算作了两个不同的排列。

所以现在的关键在于，如何设计剪枝逻辑，把这种重复去除掉？

答案是，保证相同元素在排列中的相对位置保持不变。

比如说nums = [1,2,2′]这个例子，我保持排列中2一直在2’前面。

这样的话，你从上面 6 个排列中只能挑出 3 个排列符合这个条件：

[ [1,2,2′],[2,1,2′],[2,2′,1] ]

这也就是正确答案。

进一步，如果nums = [1,2,2′,2”]，我只要保证重复元素2的相对位置固定，比如说2 -> 2′ -> 2”，也可以得到无重复的全排列结果。

仔细思考，应该很容易明白其中的原理：

标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复

那么反映到代码上，你注意看这个剪枝逻辑：

// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    // 如果前面的相邻相等元素没有用过，则跳过
    continue;
}
// 选择 nums[i]

当出现重复元素时，比如输入nums = [1,2,2′,2”]，2’只有在2已经被使用的情况下才会被选择，2”只有在2’已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。

参考：https://mp.weixin.qq.com/s/nrTpZ9b9RvfNsaEkJoHMvg