47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。 示例:

输入： [1,1,2] 输出：[ [1,1,2]，[1,2,1]，[2,1,1] ]

解题思路

回溯算法 类似题目：剑指 Offer 38. 字符串的排列

相比【全排列】这题，【全排列II】中含有重复元素，但是输出的排列不能含有重复的排列。
可以对原始数组先进行排序，这样相同的元素都集中到一起了。
在得到一个全排列的时候，我们总是从位置0递归到位置n-1，所以对于含有重复元素的序列，如112，第1层第1个位置+第2层第2个位置+第3层第3个位置会得到112这个排列，如果不排除重复的序列，那么原本第1层第2个位置+第2层第1个位置+第3层第3个位置也会得到112这个排列。
但是我们需要剔除掉这些重复的排列，所以其实对于位置2的这个1，其与位置1的1相同，没必要再往下一层，重复刚才的故事。那怎么跳过这个1呢，我们发现这个1与前面的1位于同一层，并且因为当前访问的是位置2的1，前面位置1的1在上一次回溯的时候已经取消了使用标记，所以跳过的判断条件如下：
if (i > 0 && orgNums[i] == orgNums[i-1] && !used[i-1]) continue
代码实现

/*
           1                         1                             2
  1        1       2      |   1      1        2       |     1      1       2
1 1 2    1 1 2   1 1 2      1 1 2   1 1 2     1 1 2       1 1 2   1 1 2    1 1 2
*/
#include<algorithm>
class Solution {
public:
    vector<vector<int>> res;
    vector<bool> used;//标记原始数组中已经被使用的位置
    vector<int> orgNums;
    vector<int> solOne;
    int orgLen;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        orgNums = nums;
        sort(orgNums.begin(),orgNums.end());
        orgLen = nums.size();
        for (int i = 0;i < orgLen;i++)
            used.push_back(false);
        dep();
        return res;
    }
    void dep() {
        if (solOne.size() == orgLen ) {
            res.push_back(solOne);
            return;
        }
        for (int i = 0;i < orgLen;i++) {
            if (!used[i]){
                /*
                 !used[i-1] 代表本层orgNums循环，
                 并且orgNums中排在自己前面一个数字已经被清空使用标记，必须要判断要有!used[i-1] 
                 才能保证是去重同一层的，而不是误去充了不同层不同位置相同的数
                */
                if (i > 0 && orgNums[i] == orgNums[i-1] && !used[i-1])
                    continue;
                solOne.push_back(orgNums[i]);
                used[i] = true;
                dep();
                //撤销选择，回退
                used[i] = false;
                solOne.pop_back();
            }
        }
    }
};