LeetCode 筆記 - 216. Combination Sum III

Posted on

題目在此 216. Combination Sum III

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

解題思維

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

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

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

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

也許你也會想看看