題目出處

216. Combination Sum III

難度

medium

個人範例程式碼

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

        if k > 9: # only 1-9 can use
            return []

        ans = []
        self.dfs(1, n, k, [], ans)
        return ans

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

        if k < 0:
            return

        # define and split
        for i in range(start_num, 10): # 1 - 9
            combinations.append(i) 
            self.dfs(i+1, target-i, k-1, combinations, ans)
            combinations.pop() # backtracking

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

算法說明

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

組合類的問題，使用 dfs 搜尋出全部的組合

我們能使用的數字只有 1-9，用 range 取範圍時要注意「range(1,10)」，才會取到 9

input handling

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

Boundary conditions

用 dfs 來控制搜尋範圍，直到 「k = 0 時，進行結果判斷」 或 「k < 0 時，直接 return」

Reference