題目出處
難度
medium
個人範例程式碼
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates:
return []
ans = []
self.dfs(candidates, target, 0, [], ans)
return ans
def dfs(self, candidates, target, start_idx, combination, ans):
# end of recursion
if target < 0:
return
if target == 0:
ans.append(list(combination)) # deepcopy
return
# define and split
for idx in range(start_idx, len(candidates)):
combination.append(candidates[idx])
self.dfs(candidates, target-candidates[idx], idx, combination, ans) # idx + 1 = next index
combination.pop()
算法說明
本題是 Combinations 系列的第 2 題，前面的題目可以參考：
第 1 題：不允許重複，給定數字範圍的全部組合，目標是指定組合內固定的數量。
第 2 題：允許重複，順序不同視為相同結果，也就是說「(1,2,3) 與 (3, 2, 1) 是一個結果」
第 3 題：允許有限重複(題目指定上限數量)，求全部組合。
第 4 題：不允許重複，給定數字範圍的全部組合，目標是求指定的和。
第 5 題：允許重複，但順序不同視為不同結果，也就是說「(1,2,3) 與 (3, 2, 1) 是兩個結果」。(這題已經可以當作排列的題目了。)
組合類的問題，使用 dfs 搜尋出全部的組合，在判斷可行的方案。
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
如果沒有 candidates，直接 return []
Boundary conditions
見上述說明