[LeetCode解題攻略] 47. Permutations II

題目描述

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

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

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

解題思路

此題與 LeetCode 46. Permutations 非常相似，不同的是，輸入的數組可能包含重複的元素，因此我們需要確保返回的排列是唯一的。

解決此問題的關鍵是避免重複。可以採用以下方法：

1. 排序數組：對輸入數組進行排序，讓相同的數字相鄰排列，便於去重。
2. 跳過重複元素：在遞迴過程中，如果當前元素與前一個元素相同，且前一個元素尚未使用，則跳過。

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

思路

使用回溯法生成排列，並在選擇元素時進行去重處理：

1. 將數組排序，讓重複的數字相鄰。
2. 使用一個布林數組 used 來標記哪些元素已經被使用。
3. 如果當前數字與前一個數字相同，且前一個數字尚未被使用，則跳過當前數字，避免生成重複的排列。

程式碼

class Solution:
    def permuteUnique(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 used[i]:
                    continue
                # 跳過重複的元素
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue
                
                # 選擇當前元素
                used[i] = True
                path.append(nums[i])
                backtrack(path, used, res)
                # 回溯：撤銷選擇
                path.pop()
                used[i] = False

        nums.sort()  # 排序以便去重
        res = []
        used = [False] * len(nums)
        backtrack([], used, res)
        return res

時間與空間複雜度

• 時間複雜度：O(n×n!)
• • 排列的總數最多為 n!，生成每個排列需要 O(n) 的時間。
  • 去重的檢查操作並未改變時間複雜度。
• 空間複雜度：O(n)
• • 使用了遞迴和布林數組 used。

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

思路

1. 使用交換法來構造排列。
2. 在每次交換之前，檢查是否出現重複元素，避免生成重複的排列。
3. 通過集合來記錄當前層的已選擇元素，避免重複交換。

程式碼

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start, res):
            if start == len(nums):
                res.append(nums[:])  # 儲存當前排列
                return
            
            seen = set()  # 用來記錄本層中已使用的數字
            for i in range(start, len(nums)):
                # 如果當前數字已被使用，則跳過
                if nums[i] in seen:
                    continue
                seen.add(nums[i])
                # 交換當前數字到起始位置
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1, res)
                # 回溯：交換回來
                nums[start], nums[i] = nums[i], nums[start]

        nums.sort()  # 排序以便去重
        res = []
        backtrack(0, res)
        return res

時間與空間複雜度

• 時間複雜度：O(n×n!)
• • 排列的總數最多為 n!，生成每個排列需要 O(n) 的時間。
• 空間複雜度：O(n)
• • 使用了遞迴和集合 seen。

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

思路

1. 使用 Python 的內建函數 itertools.permutations 生成所有排列。
2. 利用集合自動去重。

程式碼

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

時間與空間複雜度

• 時間複雜度：O(n×n!)
• • 生成所有排列並去重的時間開銷為 O(n×n!)。
• 空間複雜度：O(n!)
• • 儲存所有唯一排列的集合。

結論

1. 回溯演算法 是最直觀的方法，適合手動實現和學習。
2. 遞迴與交換法 是對性能稍作優化的版本。
3. 如果追求快速實現，使用 內建函數 是不錯的選擇。

希望這篇教學能幫助大家輕鬆理解這道題目！