EPISODE:110

LeetCode 筆記 - 216. Combination Sum III

發佈: 2022.06.25
閱讀: 約 1 分鐘
字數: 243

挑戰從數字 1 到 9 中找出特定長度且總和等於目標值的組合。本文利用深度優先搜尋（DFS）進行窮舉，透過遞迴探索與邊界剪枝，能高效地找出所有符合限制的數字組合。這是一篇掌握回溯（Backtracking）技巧的進階練習。

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 216. Combination Sum III

給定目標數，請從 1 ~ 9 找出相加組合，每個數字只能用一次

解題思維

如果沒解過第一題可以看 LeetCode 筆記 - 39. Combination Sum
如果沒解過第二題可以看 LeetCode 筆記 - 40. Combination Sum II

這題一樣是用 Depth First Search 跑一次就可以了

這裡沒用到什麼新技巧，換個角度做一樣的事

程式碼

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        
        candidates = [n for n in range(1, 10)]
        self.result = []
        
        def dfs(last_index, result, count, level):
            if level == k:
                if count == n:
                    self.result.append(result)
                return
            
            for i in range(last_index + 1, 9):
                if count + candidates[i] > n:
                    break
                
                dfs(i, result + [candidates[i]], count + candidates[i], level + 1)
                
        dfs(-1, [], 0, 0)
        
        return self.result

也許你也會想看看