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

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

題目出處

77. Combinations

難度

medium

個人範例程式碼

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        if not n or not k:
            return [[]]

        elements = [i for i in range(1, n+1)]
        ans = []
        self.dfs(elements, k, [], ans)

        return ans

    def dfs(self, elements, k, combinations, ans):
        # end of recursion
        if k <= 0:
            ans.append(combinations[:]) # deepcopy
            return 

        if not elements:
            return

        # define and split
        for i, element in enumerate(elements):
            combinations.append(element)
            self.dfs(elements[i+1:], k-1, combinations, ans)
            combinations.pop() # backtracking

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

算法說明

本題是 Combinations 系列的第 1 題,其他的題目可以參考:
第 1 題:不允許重複,給定數字範圍的全部組合,目標是指定組合內固定的數量。
第 2 題:允許重複,順序不同視為相同結果,也就是說「(1,2,3) 與 (3, 2, 1) 是一個結果」
第 3 題:允許有限重複(題目指定上限數量),求全部組合。
第 4 題:不允許重複,給定數字範圍的全部組合,目標是求指定的和。
第 5 題:允許重複,但順序不同視為不同結果,也就是說「(1,2,3) 與 (3, 2, 1) 是兩個結果」。(這題已經可以當作排列的題目了。)

組合類的問題,使用 dfs 搜尋出全部的組合,
記得當 k = 4 時,實際上我們可用的數字是 「1,2,3,4」而非 「0,1,2,3」。

input handling

如果沒有 k 或 n,直接 return [[]]

Boundary conditions

用 dfs 來控制搜尋範圍,直到 「k <= 0」 或 「找不到新的元素」,return 結果

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 DictionaryBFS (拓樸)GraphPython
[Lint] 431Connected Component in Undirected GraphBFS (連通塊)GraphPython