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

➣ Reading Time: 5 minutes

題目出處

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

Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!

文章: 728

★留個言吧!內容有誤或想要補充也歡迎與我討論!