題目出處

47. Permutations II

難度

medium

個人範例程式碼

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return nums

        nums.sort()
        self.ans = []
        self.dfs(nums, [])
        return self.ans

    def dfs(self, nums, permutations):
        # end of recursion
        if not nums:
            self.ans.append(list(permutations))
            return

        # define and split
        for i, num in enumerate(nums):
            if i > 0 and nums[i] == nums[i-1]: # if duplicate, we only record first time
                continue  

            permutations.append(num)
            self.dfs(nums[:i] + nums[i+1:], permutations)
            permutations.pop() # backtracking

算法說明

• 此題目的前一題，差別在這題需要多處理重複的元素，可參考：

【Leetcode】python – [46] Permutations 個人解法筆記 #重要題型

排列類型的題目，使用 dfs 去搜尋全部的結果

處理順序

另外在處理順序時，我們使用傳入「start[0:i] + start[i+1:]」的方式，暫時移除了 start[i] 的元素，
這樣的操作方式會複製一個新的 list，而不會影響到原本的 list

處理重複

為了處理重複，我們先對 nums 進行排序，我們使用

nums.sort()

另外在處理重複的數字時，我們只採用第一組的結果，後面都 continue 掉，因此：

if i > 0 and nums[i] == nums[i-1]: # if duplicate, we only record first time
    continue  

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

當沒有 nums 時，return nums

Boundary conditions

搜尋至 no nums 時，添加結果回傳 (表示元素已使用完畢)

Reference

• 带重复元素的排列 · Permutations II