題目出處

難度

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 結果

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