---
title: "47. Permutations II"
url: "https://laigary.com/interview/coding/47-permutations-ii"
type: "note"
section: "coding"
date: "2023-01-27"
updated: "2026-07-26"
tags: ["Backtrack", "Classic"]
---

# 47. Permutations II

[47\. Permutations II](https://leetcode.com/problems/permutations-ii/)

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

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

## 思路

和 [46. Permutations](/interview/coding/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](/interview/coding/90-subsets-ii)、[40. Combination Sum II](/interview/coding/40-combination-sum-ii)，所以路線二比較值得練熟。

## 解題方向

### 路線一：Counter 按值枚舉

```python
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` 的**值**是安全的（鍵沒有變動），所以不會遇到「迭代時改字典」的錯誤。

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

```python
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](/interview/coding/46-permutations) 一模一樣，只多了排序和那一行跳過條件 —— 這是它的價值：**同一個模板改一行就處理了去重**。

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

## 補充

**兩條路線的取捨**：

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

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

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

骨架整理見 [Backtracking 模板](/interview/coding/backtracking-template)。

## 複雜度

- 時間 $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 種。**去重的價值就在這裡**：它不只是過濾輸出，而是根本不去走那些會產生重複的分支。