題目描述

給定一個(gè)可包含重復(fù)數(shù)字的序列 nums ，按任意順序 返回所有不重復(fù)的全排列。

示例 ：

• 輸入：nums = [1,1,2]
• 輸出：
  [[1,1,2],
  [1,2,1],
  [2,1,1]]
  b站題目解讀講的不好，勿噴

解題思路

首先選擇對(duì)原數(shù)組排序，保證相同的數(shù)字都相鄰，然后每次填入的數(shù)一定是這個(gè)數(shù)所在重復(fù)數(shù)集合中「從左往右第一個(gè)未被填過(guò)的數(shù)字」，即如下的判斷條件：

if (i > 0 && nums[i] == nums[i - 1] && used[i-1] == false) {continue;
}

即可實(shí)現(xiàn)樹(shù)層的去重。

• 希望在計(jì)算的過(guò)程中進(jìn)行去重操作，所以我們對(duì)數(shù)組nums排序處理。

• 如果nums[i] == nums[i-1]就說(shuō)明該分支有可能是重復(fù)的。 但是這個(gè)相等條件有兩種可能:

1. 一種是，1 1‘ 2，也就是選擇完1之后再選擇第二個(gè)1，兩個(gè)元素雖然重復(fù)，但是第二個(gè)元素是前一個(gè)元素的下一層，這時(shí)是沒(méi)有問(wèn)題的。
2. 另一種是之前的 同層 分支已經(jīng)有 1 1‘ 2了，這次的選擇是 1‘ 1 2 。兩個(gè)元素重復(fù)，且重的是同層路徑。那就說(shuō)明是重復(fù)分支。

具體區(qū)分的辦法是 nums[i-1] 的used狀態(tài)是被選擇的，那么說(shuō)明當(dāng)前的nums[i] 是 nums[i-1]的下一層路徑。 否則如果 nums[i-1] 的狀態(tài)是沒(méi)被選擇的，那么說(shuō)明當(dāng)前 的nums[i] 是nums[i-1] 同層路徑。

代碼

class Solution {
public:
// [] 中的數(shù)字可以重復(fù)，結(jié)果集的vector元素不能重復(fù)vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());vector<bool> used(nums.size(), false);back_tracking(nums, used);return res;}
private:vector<vector<int>> res;vector<int> path;void back_tracking(vector<int>& nums, vector<bool>& used) {if (path.size() == nums.size()) {res.push_back(path);return;} else {for (int i = 0; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;if (used[i] == false) {used[i] = true;path.push_back(nums[i]);back_tracking(nums, used);path.pop_back();used[i] = false;}}}} 
};

說(shuō)明

去重最關(guān)鍵的代碼就是

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;
}

而改成used[i-1]==true也正確

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {continue;
}

樹(shù)層上去重(used[i - 1] == false)，的樹(shù)形結(jié)構(gòu)如下：
樹(shù)枝上去重（used[i - 1] == true）的樹(shù)型結(jié)構(gòu)如下：