46. Permutations

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

46. Permutations

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

思路

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

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

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

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

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

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

解題方向

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（有重複元素）時才不用重寫。

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

補充

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

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

同一個模板的其他題：78. Subsets、77. Combinations、39. Combination Sum。骨架整理見 Backtracking 模板。

複雜度

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

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