47. PermutationsII 全排列2

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]
 ]

跟上道题不一样的地方就是会有重复的数字

 vector<vector<int>> permuteUnique(vector<int>& nums) {
 	// 这里用set来去重,因为递归回退的时候可能会有重复的元素
    set<vector<int>> res{};
    if (nums.size()==0) return vector<vector<int>>();
    sort(nums.begin(), nums.end());
    permuteUniqueCore(res, nums, 0, nums.size());
    return vector<vector<int>> (res.begin(),res.end());
}
    
void permuteUniqueCore(set<vector<int>> &res,vector<int> &nums,int k,int n){
    if (k == n) {
        printArr(nums);
        res.insert(nums);
        return;
    }
    for (int i = k; i<n; i++) {
        if (nums[k]==nums[i] && i!=k) {
            continue;
        }
        swap(nums[i], nums[k]);
        permuteUniqueCore(res, nums, k+1, n);
        swap(nums[i], nums[k]);
    }
}
 
comments powered by Disqus