[LeetCode解題攻略] 46. Permutations

題目描述

給定一個不含重複數字的整數陣列 nums，返回所有可能的排列。

範例 1：

輸入: nums = [1, 2, 3]
輸出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

輸入: nums = [0, 1]
輸出: [[0,1],[1,0]]

範例 3：

輸入: nums = [1]
輸出: [[1]]

解題思路

這是一道經典的排列組合問題。對於給定的數組，我們需要找到所有元素的排列組合。有幾種方法可以實作。

解法一：回溯演算法 (Backtracking)

思路

回溯法是解決排列組合問題的常用方法。主要步驟如下：

1. 使用一個遞迴函數來構造每種排列。
2. 使用一個布林數組來標記哪些元素已經被選中。
3. 當排列長度等於 nums 長度時，將當前排列加入結果。
4. 回溯時取消當前選擇，繼續探索其他可能性。

程式碼

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(path, used, res):
            # 當排列長度等於輸入長度，將排列加入結果
            if len(path) == len(nums):
                res.append(path[:])  # 複製當前排列
                return
            
            for i in range(len(nums)):
                if not used[i]:  # 如果該數字未被使用
                    # 選擇當前數字
                    used[i] = True
                    path.append(nums[i])
                    # 繼續遞迴
                    backtrack(path, used, res)
                    # 回溯：撤銷選擇
                    path.pop()
                    used[i] = False

        res = []
        used = [False] * len(nums)  # 用來標記元素是否被使用
        backtrack([], used, res)
        return res

時間與空間複雜度

• 時間複雜度：O(n×n!)
• • 每個排列長度為 n，有 n! 種排列組合。
• 空間複雜度：O(n)
• • 使用了 backtrack 函式以及 used 陣列。

解法二：遞迴與交換法 (Recursive Swapping)

思路

1. 將 nums 視為一個待排列的陣列。
2. 透過交換元素來構造每種排列。
3. 每次將當前位置的數字與其後任意位置的數字交換，遞迴處理後續排列。
4. 回溯時將數字交換回來。

程式碼

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start, res):
            # 當起始位置等於陣列長度時，將排列加入結果
            if start == len(nums):
                res.append(nums[:])  # 複製當前排列
                return
            
            for i in range(start, len(nums)):
                # 交換當前數字到起始位置
                nums[start], nums[i] = nums[i], nums[start]
                # 繼續遞迴
                backtrack(start + 1, res)
                # 回溯：交換回來
                nums[start], nums[i] = nums[i], nums[start]

        res = []
        backtrack(0, res)
        return res

時間與空間複雜度

• 時間複雜度：O(n×n!)
• • 同樣需要生成所有排列，且每個排列長度為 n。
• 空間複雜度：O(n)
• • 由遞迴深度決定。

解法三：內建函數 (Python itertools.permutations)

思路

1. Python 提供了 itertools.permutations，可以直接生成所有排列。
2. 使用該函數可以大幅簡化程式碼。

程式碼

from itertools import permutations
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(permutations(nums))

時間與空間複雜度

• 時間複雜度：O(n×n!)
• • itertools.permutations 底層也是基於生成所有排列。
• 空間複雜度：O(n!)
• • 儲存所有排列。

結論

1. 回溯演算法 是最常用的手動實現方法，適合理解排列生成的過程。
2. 遞迴與交換法 適合追求更少空間開銷的情況。
3. 如果時間緊迫，可以直接使用 內建函數。

希望這篇解題教學對大家有幫助！