LeetCode 47. Permutations II

用回溯法完成，跟普通排列问题不同的是，需要排除掉一些重复“路径”。
可以这样做，先把输入数组排个序，这样重复的数就在相邻位置了。随后在回溯探求的过程中，我们要保证相同值的两个数nums[i], nums[j]，如果i<j，那遍历只能有一种次序：nums[i]先，nums[j]后。
换句话说，就是判断这种情况是需要提前终止的：两个数nums[i]==nums[j] && i<j，但是nums[i]还没有被遍历。所以找个东西记录一下访问就行了。
时间复杂度是O(N!)，空间复杂度是O(N)

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