LeetCode 筆記 - 216. Combination Sum III

題目在此 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

也許你也會想看看