47. Permutations II

──────────────────────────────────────────────────────────────────────

47. Permutations II

有重複的數字出現，要去記錄使用的次數。

給一個可能含重複元素的陣列，回傳所有不重複的排列。

思路

和 46. Permutations 的差別只有一句：陣列裡可能有重複的值，而相同的值換位置不算不同的排列。

問題在於回溯樹本身分不出來 —— [1, 1, 2] 裡的兩個 1 在程式眼中是兩個不同的索引，所以會產生兩份一模一樣的 [1, 1, 2]。要去重有兩條路，兩條路的想法完全不同：

路線一：按「值」枚舉，而不是按「索引」

既然重複是因為「同一個值有多個索引」，那就不要用索引去枚舉。改成用 Counter 記住每個值還剩幾個，每一層對每個不同的值各試一次。同一個值只會被試一次，重複自然消失。

這個做法的好處是不需要排序，而且邏輯很直白：「這一層我要放哪個值？」

路線二：先排序，同層跳過重複

先排序讓相同的值相鄰，然後規定：同一層裡，如果我和前一個值相同、而前一個還沒被用掉，就跳過我。

這條規則是在強制「相同的值只能按索引順序被使用」—— 第一個 1 沒用就不准用第二個 1。於是每組重複值只會產生一種使用順序，重複被消掉。

判斷條件 nums[i] == nums[i-1] and (i-1) not in visited 裡的第二項是關鍵。如果寫成 (i-1) in visited 就變成完全不同的規則，答案會少 —— 這是這題最容易寫錯的一行。

「先排序、同層跳過重複」是所有去重回溯題的共同手法，見 90. Subsets II、40. Combination Sum II，所以路線二比較值得練熟。

解題方向

路線一：Counter 按值枚舉

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtrack(curr, counter):
            if len(curr) == len(nums):
                res.append(list(curr))
                return
            for num in counter:
                if counter[num] > 0:
                    counter[num] -= 1
                    curr.append(num)
                    backtrack(curr, counter)
                    counter[num] += 1
                    curr.pop()
        backtrack([], Counter(nums))
        return res

for num in counter 走的是不同的值（Counter 的鍵），所以同一個值一層只會被選一次。counter[num] -= 1 和 += 1 就是回溯的做選擇 / 撤銷選擇。

迴圈中修改 counter 的值是安全的（鍵沒有變動），所以不會遇到「迭代時改字典」的錯誤。

路線二：排序 + 同層跳過重複

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        def backtrack(curr, visited):
            if len(curr) == len(nums):
                res.append(curr.copy())
                return
            
            for i in range(len(nums)):
                if i in visited:
                    continue
                if i > 0 and nums[i] == nums[i - 1] and (i - 1) not in visited:
                    continue
                num = nums[i]
                curr.append(num)
                visited.add(i)
                backtrack(curr, visited)
                visited.remove(i)
                curr.pop()
            
        backtrack([], set())

        return res

骨架和 46 一模一樣，只多了排序和那一行跳過條件 —— 這是它的價值：同一個模板改一行就處理了去重。

res.append(curr.copy()) 的複製不能省，理由和 46 相同（curr 是同一個 list 一路被修改）。

補充

兩條路線的取捨：

	要排序	額外空間	好處
Counter 按值枚舉	不用	$O (u)$ （`u` 是相異值個數）	邏輯直白，不用記那行條件
排序 + 跳過重複	要	$O (n)$	和 90 / 40 共用同一套手法

路線二比較值得練，因為它是可遷移的模板；不想排序的話路線一就是答案。

同一組去重手法的題目：90. Subsets II（子集版，條件是 i > start）、40. Combination Sum II。注意子集 / 組合題的條件寫的是 i > start 而不是 i > 0 —— 因為那類題目的「同一層」由 start 界定，而排列題的同一層是整個迴圈。

骨架整理見 Backtracking 模板。

複雜度

時間 $O (n \times n!)$ 上界 — 有重複時實際產生的排列數少於 n!，去重讓搜尋樹被剪掉一部分，但最壞情況（全部相異）就是 n! 個結果，每個花 $O (n)$ 複製
空間 $O (n)$ — 遞迴深度 n，加上 curr 與 visited / counter（不含輸出）

其中 n 是元素個數。

精確的排列數是 $\frac{n!}{\prod c_{i}!}$ （c_i 是每個相異值的出現次數）—— 例如 [1,1,2] 只有 3 種而不是 6 種。去重的價值就在這裡：它不只是過濾輸出，而是根本不去走那些會產生重複的分支。