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

➣ Reading Time: 4 minutes

題目出處

46. Permutations

難度

medium

個人範例程式碼

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

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

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

        # define and split
        for i, num in enumerate(nums):
            permutations.append(num)
            # temporarily remove element i = start[0:i] + start[i+1:]
            self.dfs(nums[:i] + nums[i+1:], permutations)
            permutations.pop() # backtracking

算法說明

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

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

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

input handling

當沒有 nums 時,return nums

Boundary conditions

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

Reference

Howard Weng
Howard Weng

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

文章: 693

1 則留言

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