0047. 全排列 II [Medium] [Permutations II].md

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

---

题目： 对给定的数组nums进行全排列，其中nums可能包含重复的元素。返回的全排列集合中应是无重复的解的（去重的）。

思路： 同Permutations。记p为一个待填充的排列，当p的长度等于数组nums的长度时，表明已经找到了一种排列。针对p的同一个位置，为了不出现重复的排列，回溯返回后继续循环时需要跳过已经使用过的元素值。比如p[1]以值为3进行递归，当递归回溯到p[1]这个状态时，p[1]的下一个取值应该跳过值同样为3的元素（因此最开始需要对nums进行排序），然后再递归进入p[2]状态，依次类推。

工程代码下载

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return {};

        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> vec;
        vector<bool> used(n, false);

        helper(nums, res, vec, used);

        return res;
    }
private:
    void helper(vector<int>& nums, vector<vector<int>>& res, vector<int>& vec,
               vector<bool>& used){
        if(vec.size() == nums.size()){
            res.push_back(vec);
            return;
        }

        for(int i = 0; i < nums.size(); ++i){
            if(used[i] == true)
                continue;
            // 如果当前数与前一个数相等，并且前一个没被使用过，则跳过这个重复的元素
            if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false)
                continue;
            used[i] = true;
            vec.push_back(nums[i]);
            helper(nums, res, vec, used);
            vec.pop_back();
            used[i] = false;
        }

        return;
    }
};

int main()
{
    Solution sln;
    vector<int> testcase{ 1,1,2,2,2,2,2,2,2,2 };
    vector<vector<int>> res;
    res = sln.permuteUnique(testcase);
    for (auto vec : res) {
        for (auto i : vec)
            cout << i << " ";
        cout << endl;
    }
    std::cout << "Hello World!\n";
}