LeetCode 筆記 - 39. Combination Sum

題目在此 39. Combination Sum

給一個數列與目標數,請從數列找出相加的組合等於目標數,數字可以重複使用

解題思維

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

有個小技巧是可以先 Sorting,來跳過一些計算

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

candidates.sort()

self.result = []
def dfs(last_index, result, count):
if count == target:
self.result.append(result)
return

for i, candidate in enumerate(candidates):
if i < last_index:
continue
if count + candidate > target:
break

dfs(i, result + [candidate], count + candidate)

dfs(-1, [], 0)

return self.result

相關文章