力扣日記：【回溯算法篇】47. 全排列 II

日期：2023.2.22
參考：代碼隨想錄、力扣

47. 全排列 II

題目描述

難度：中等

給定一個可包含重復數字的序列 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

題解

cppver

class Solution {
public:vector<int> path;vector<vector<int>> result;vector<vector<int>> permuteUnique(vector<int>& nums) {// 排序sort(nums.begin(), nums.end());vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}void backtracking(vector<int>& nums, vector<bool>& used) {  // 因為存在重復值，所以不宜用哈希表記錄是否使用過// 終止條件if (path.size() == nums.size()) {result.push_back(path);return;}int lastNum = -11;// for 橫向遍歷for (int i = 0; i < nums.size(); i++) {// 需要標記哪些值已經取過了 used[i] if (used[i] == true) continue;  // 取過了，則跳過該值// 去重if (nums[i] == lastNum) continue; // 與for循環的上一次取值重復// 否則，標記取過，并進行取值與遞歸used[i] = true;lastNum = nums[i]; // 更新 lastNumpath.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}
};

復雜度

時間復雜度：
空間復雜度：

思路總結

• 本題與 46. 全排列 的區別在于，集合中可能存在重復元素。因此，需要考慮去重，即在46題的基礎上，需要在for循環遍歷（橫向遍歷）中，過濾掉相同的元素（但又不能影響到縱向遞歸時元素的可重復選取）。
• 不同于 40.組合總和 II 和 90.子集 II，全排列在for循環遍歷時不能使用startindex，即每次for循環遍歷都會從頭開始遍歷，不能直接在for循環中，用 if (i > 0 && nums[i] == nums[i-1]) continue; 來跳過重復元素，因為這樣會使得在縱向遞歸時也無法選取到重復元素。
• 因此，需要一個只會影響到橫向遍歷的變量，即代碼中在for循環前定義的lastNum（這樣每次for循環前會重置lastNum），用來記錄相同層中for循環上次取到的元素——如果當前值與for循環上次取到的值相同，則跳過當前元素。且只有在該值也滿足“縱向遞歸中當前位置未取過”的條件（used[i] == false）才會更新該lastNum（即當前值能進行取值、遞歸才會更新）。
• 注意：
  • 去重 要提前做好排序。
  • 由于本題存在重復元素，所以不能使用按值大小記錄是否取過的哈希表作為used，而要使用按位置記錄的used（vector<bool> used(nums.size(), false)）。
  • 去重與是否使用過的if-continue判斷條件的前后位置不影響（也可以寫在一起），但取值、更新、遞歸、回溯等（所謂處理節點）一定要放在兩者后面。
• 樹形結構示意圖：
  •