LeetCode Permutations 全排列 Python 遞歸解法

題目

給定無重複元素數組 nums，返回其所有全排列。

示例：[1,2,3] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。

解題思路：回溯遞歸

1. 維護 current 當前排列，remaining 剩餘可選元素。
2. 遞歸：遍歷 remaining，依次加入 current，遞歸處理剩餘元素。
3. 終止條件：remaining 為空，將 current 加入結果集。
4. 回溯：撤銷最後選擇（pop()）。

Python AC 代碼

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtrack(cur, rem):
            if not rem:
                res.append(cur[:])
                return
            for i, v in enumerate(rem):
                cur.append(v)
                backtrack(cur, rem[:i] + rem[i+1:])
                cur.pop()
        backtrack([], nums)
        return res

# 測試
if __name__ == "__main__":
    assert Solution().permute([1,2,3]) == [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

複雜度

• 時間：O(N! × N)，N! 個排列，每個複製 O(N)。
• 空間：O(N) 遞歸棧 + O(N) 當前路徑（不計輸出空間）。

優化提示

• 用 used 布爾數組 + 原地交換（swap）可省去切片開銷。
• Python itertools.permutations 一行解決，但面試需手寫回溯邏輯。