項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

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

題目出處

90. Subsets II

難度

Medium

個人範例程式碼

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

        nums.sort()

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

    def dfs(self, nums, start, combination, ans):

        ans.append(combination[:]) # deepcopy

        # end of recursion, define ans split
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]: # only take first duplicate
                continue
            combination.append(nums[i])
            self.dfs(nums, i+1, combination, ans)
            combination.pop()

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

算法說明

  • 此題的前一題為無重複版本,這題要多處理重複,可參考:

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

經典 DFS 的組合問題, 這題要多處理重複的部分,

我們先 sort() 確保有一致的順序,
我們利用 i > start 來確保跟開始項目相同時,第一組重複有被計算到

注意:不是 i > 0,而是 i > start
start 位置就是代表重複字母的第一個字,除了第一次判斷會拿之外,後面都不會再拿。

if i > start and nums[i] == nums[i-1]: # only take first duplicate
    continue

input handling

如果沒有 nums,return [[]]

Boundary conditions

用 dfs 內的 for loop 控制搜尋範圍

Reference

⭐ Leetcode 解題紀錄 ⭐題型資料結構Python SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)Python
內有 indegree, outdegree 介紹 #重要題型
207Course ScheduleBFS (拓樸)GraphPython
210Course Schedule IIBFS (拓樸)GraphPython
[Lint] 892Alien Dictionary