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

# 46. Permutations

[46\. Permutations](https://leetcode.com/problems/permutations/)

給一個**沒有重複元素**的陣列，回傳所有排列。

## 思路

排列題的回溯樹長這樣：第一層決定「第一個位置放誰」，第二層決定「第二個位置放誰」⋯⋯ 每一層都要**從全部元素裡挑一個還沒用過的**。

這就是排列和組合最根本的差別：

| | 每一層可以選什麼 | 用什麼控制 |
|---|---|---|
| **排列**（本題） | 全部元素，只要**還沒用過** | `visited` 集合 |
| **組合 / 子集**（[78](/interview/coding/78-subsets)、[77](/interview/coding/77-combinations)） | 只能選**索引比上一個大**的 | `start` 參數 |

因為排列在意順序（`[1,2]` 和 `[2,1]` 是不同答案），所以每一層都要能回頭選前面的元素，`start` 那招不能用，必須改用 `visited` 記住「這一條路徑上已經用掉哪些」。

**終止條件**是 `len(curr) == len(nums)` —— 位置填滿了就收集一份答案。

回溯的三步是固定的：**做選擇 → 遞迴 → 撤銷選擇**。這題的「選擇」是兩件事（把元素加進 `curr`、把索引記進 `visited`），所以撤銷也要對稱地做兩件事。

## 解題方向

```python
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        res = []

        def helper(curr, visited):
            if len(curr) == len(nums):
                res.append(list(curr))
                return
            
            for i in range(len(nums)):
                if i in visited:
                    continue
                num = nums[i]
                curr.append(num)
                visited.add(i)
                helper(curr, visited)
                visited.remove(i)
                curr.pop()
        
        helper([], set())

        return res
```

**`res.append(list(curr))` 那個 `list(...)` 不能省。** `curr` 是同一個 list 一路被修改，如果直接 `res.append(curr)`，收集到的會是同一個物件的參考 —— 回溯結束後全部變成空 list。這是回溯題最常見的 bug，**收集答案時一定要複製一份快照**。

**`visited` 存的是索引不是值。** 因為題目說沒有重複元素，存值也能動；但存索引是更通用的寫法，換到 [47. Permutations II](/interview/coding/47-permutations-ii)（有重複元素）時才不用重寫。

撤銷的順序 `visited.remove(i)` 然後 `curr.pop()` 和做選擇時相反，這是好習慣（像堆疊一樣後進先出），雖然這裡兩者獨立、順序其實無所謂。

## 補充

**回溯樹的形狀決定了複雜度**：第一層有 `n` 個選擇、第二層 `n-1` 個⋯⋯所以葉節點有 `n!` 個，每個葉節點還要花 $O(n)$ 複製答案。這個 $O(n \times n!)$ 是排列題的下限 —— 因為光是輸出就有那麼多內容，**沒有更快的解法**。

**有重複元素的版本**是 [47. Permutations II](/interview/coding/47-permutations-ii)：先排序，然後在同一層跳過重複的值（`if i > 0 and nums[i] == nums[i-1] and i-1 not in visited: continue`）。**「先排序、同層跳過重複」是所有去重回溯題的共同手法**，見 [90. Subsets II](/interview/coding/90-subsets-ii)、[40. Combination Sum II](/interview/coding/40-combination-sum-ii)。

**同一個模板的其他題**：[78. Subsets](/interview/coding/78-subsets)、[77. Combinations](/interview/coding/77-combinations)、[39. Combination Sum](/interview/coding/39-combination-sum)。骨架整理見 [Backtracking 模板](/interview/coding/backtracking-template)。

## 複雜度

- 時間 $O(n \times n!)$ — 有 `n!` 個排列，每個要花 $O(n)$ 複製進結果
- 空間 $O(n)$ — 遞迴深度 `n`，加上 `curr` 和 `visited` 各 $O(n)$（不含輸出）

其中 `n` 是元素個數。輸出本身佔 $O(n \times n!)$，如果把它算進去，空間也是那個量級。