題目

給定一個可包含重復數字的序列?nums?，按任意順序?返回所有不重復的全排列。

示例 1：

輸入：nums = [1,1,2]
輸出：
[[1,1,2],[1,2,1],[2,1,1]]

示例 2：

輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

思路

????????為了得到不重復的所有排列組合，我們對輸入數組進行排序，讓相同的元素相鄰排列，這樣在后續的回溯過程中，能更方便地判斷和避免重復排列。然后創建一個標記數組visit，看這個數字是否已被使用，保證每個元素在一個排列中僅使用一次。在hs中，將未使用的元素添加到當前排列中，然后在檢查元素是否已被使用，還會檢查當前元素是否和前一個元素相同，并且前一個元素未被使用。如果滿足這個條件，就跳過當前元素，避免生成重復排列。在遞歸調用結束后，將元素標記為未使用，并從當前排列中移除該元素，這樣就可以嘗試其他可能的排列。?

代碼

class Solution {
public:vector<int> visit;//用來標記訪問過的數void hs(vector<int>& nums,vector<vector<int>>& res,int index,vector<int>& n){if (index==nums.size())//n里面已經把nums里所有的數字都填充進來了{res.emplace_back(n);return;}for(int i=0;i<nums.size();i++) {//當前數字已被訪問過或當前數字與前一個數字大小相等并且前一個數字未被訪問if (visit[i]||(i>0&&nums[i]==nums[i-1]&&!visit[i - 1])){continue;//跳過當前循環，進入下一層}n.emplace_back(nums[i]);//符合條件，放入nvisit[i]=1;//把當前數字標記為已訪問hs(nums,res,index+1,n);//從下一個數開始進行遞歸visit[i] = 0;//把當前數字標記為未訪問并從n中移除，嘗試其他排列n.pop_back();}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> res;//結果數組vector<int> n;//存每種組合的數組visit.resize(nums.size());//把visit數組的大小調整成nums數組的大小sort(nums.begin(),nums.end());//對nums排序，方便把重復的數字放在一起hs(nums,res,0,n);//遞歸進行全排列return res;}
};