題目描述:給定一個不含重複元素的整數陣列 nums,回傳其所有可能的全排列。
解題思路:全排列需要每個元素恰好出現一次,且元素順序不同視為不同排列,共有 n! 種。使用回溯法搭配 visited 布林陣列:每次從所有尚未使用的元素中選一個加入路徑,遞迴至路徑長度等於 n 時即為一個完整排列。選定元素前標記為已使用(visited[i] = true),遞迴返回後取消標記(visited[i] = false)以還原狀態,繼續嘗試其他元素。另一種等價方法是「原地交換法(swap)」:在遞迴中將 nums[start] 與 nums[i] 交換後遞迴,結束後再換回,省去額外的 visited 陣列。
時間複雜度:O(n · n!) — 共有 n! 個排列,每個排列複製至答案需 O(n) 時間,因此總時間為 O(n · n!)。遞迴樹本身的節點數也是 O(n · n!) 量級。
空間複雜度:O(n) — 遞迴堆疊深度為 n,visited 陣列與 path 各佔 O(n) 空間(不計輸出空間)。
1. Initialize visited array of size n, all false
2. Define backtrack(path):
a. If len(path) == n: append copy of path to result; return
b. For i from 0 to n-1:
i. If visited[i]: continue
ii. Mark visited[i] = true
iii.Push nums[i] onto path
iv. Recurse: backtrack(path)
v. Pop last element from path
vi. Mark visited[i] = false
3. Call backtrack([])
4. Return result原地交換法 O(n · n!):避免 visited 陣列,直接在 nums 上操作。將 nums[start] 與 nums[i] 交換,以 start+1 遞迴,結束後交換回來。程式碼更簡潔,且不需額外的 path 陣列,但會修改原始陣列的順序。
next_permutation 迭代法 O(n · n!):反覆呼叫 std::next_permutation 直至回傳 false(完整循環一遍)。程式碼極短,但須先對陣列排序,且不易理解其回溯本質。