39. Combination Sum

Question: Combination Sum

Solution

想法：

用 list 中的 element，可以重複放，所以遞迴時

• 第一個數字選 2，後面仍可以選 2 [2]
  • 後面選 2，仍可以選 2 [2, 2, …]
  • 後面不選 2，後面的組合有一個 2 [2, …]
• 第一個數字沒有 2，後面只能選 3, 6, 7 [3, …] [6, …] [7, …]
• Backtracking → DFS
• 終止條件：
  • 每次遞迴，target - nums[i]，
    • == 0 時 append combination 到 res，return
    • < 0 時 return
• 遞迴條件：
  • 遞迴時，先將 element append 到 combination 中
    進入遞迴，可以使用重複的數字 dfs(i)
  • 遞迴結束後，再 pop() 將 combination 回復原狀
    進入遞迴，只能選下一個數字 dfs(i + 1)

Time Complexity: O(2 ^ target)

2 的樹高(h) 次方

class Solution:

def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:

res = list()

combination = list()

def dfs(i, residule):

if residule == 0:

res.append(combination.copy())

return

elif residule < 0 or i > len(candidates) - 1:

return

else:

combination.append(candidates[i])

dfs(i, residule - candidates[i])

combination.pop()

dfs(i + 1, residule)

dfs(0, target)

return res

Video Solution