# **Leetcode筆記(Combination Sum)** :::info :information_source: 題目 : Combination Sum, 類型 : dynamic programming , 等級 : medium 日期 : 2023/02/25，2023/04/22，2023/05/02，2023/07/10，2023/10/11，2023/12/02，2024/10/22，2025/03/04 ::: ### 嘗試 ```python class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: dp = [0] * (target + 1) for i in range(target + 1): for j in range(len(candidates)): if i == j: dp[i] = 1 dp[i] = max(dp[i], dp[i - j] + dp[j]) return dp[target] # 只會求出數量 ``` 2023/05/02，需要紀錄starting point，不然會有重複配對的問題 ```python class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] def backtracking(remain, combination, start_index): if remain == 0: res.append(combination.copy()) return if remain < 0: return # 要記錄starting point 不然會有重複配對的問題 # 規定只能往後配對 for i in range(start_index, len(candidates)): combination.append(candidates[i]) backtracking(remain - candidates[i], combination, i) combination.pop() backtracking(target, [], 0) return res ``` 2023/07/10 永遠往後尋找，這樣就不會有重複的 1. 起始點永遠為自己(可重複) or 比自己更大的數 2. 需要starting point 3. path要remove，因為要還一個空的path給下一個數字 4. path需要被copy()，不然之後的跌代，此path就會變 ```python class Solution: def __init__(self): self.res = list() def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(starting, total, path): if total == target: self.res.append(path.copy()) return if total > target: return for i in range(starting, len(candidates)): path.append(candidates[i]) dfs(i, total + candidates[i], path) path.remove(candidates[i]) return dfs(0, 0, []) return self.res ``` 2023/10/11 for i in range(starting, len(candidates)): ```python class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] def dfs(starting, total, path): if total == target: res.append(path.copy()) return if total > target: return for i in range(starting, len(candidates)): dfs(i, total + candidates[i], path + [candidates[i]]) return for i, n in enumerate(candidates): dfs(i, n, [n]) return res ``` 2023/12/02 ```python class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] def backtracking(starting, total, subRes): if total == target: res.append(subRes.copy()) return if total > target: return for i in range(starting, len(candidates)): n = candidates[i] subRes.append(n) backtracking(i, total + n, subRes) subRes.remove(n) return backtracking(0, 0, list()) return res ``` 2024/10/22 昨天收到google Taiwan面試，還好沒有放棄刷題，感謝在看不見希望還努力刷題的自己 ```python class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: self.res = [] self.backtracking(candidates, target, [], 0) return self.res def backtracking(self, candidates, target, path, start): if sum(path) == target: self.res.append(path) if sum(path) > target: return for i in range(start, len(candidates)): self.backtracking(candidates, target, path + [candidates[i]], i) ``` 2025/03/04 今天有一點被困住，想說在backtracking那部份，為什麼每一個都要加上n，考慮到當前的n，想說如果有些組何不用n呢。原因是因為，這些不同n會在for迴圈被考慮，例如[2,3,6,7]，會有[2,6]的這個組合出現，在第一次考慮2後，第二次可以考慮[2,3,6,7]，就會有[2,6]此組合出現 ```python class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] self.backtracking(candidates, target, 0, 0, [], res) return res def backtracking(self, candidates, target, starting, total, path, res): if total > target: return elif total == target: res.append(path) for i in range(starting, len(candidates)): n = candidates[i] self.backtracking(candidates, target, i, total + n, path + [n], res) ``` --- ### **優化** 時間複雜度：O(N^target)，其中 N 是 candidates 的數量，target 是目標值。每個元素都可以重複使用，因此有 N^target 種可能的組合。在最壞情況下，遞歸樹的高度為 target，因此需要總共的運行時間為 O(N^target)。 空間複雜度：O(target)，因為我們需要在遞歸過程中存儲組合，並且最多有 target 層遞歸調用。此外，輸出數組 res 也需要 O(N^target) 的空間。 ```python class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] def backtracking(remain, combination, start_index): # 找到解法 if remain == 0: # 可能是因為combination為[]在全域已被定義 # 所以copy可以把目前的combination抓住 res.append(combination.copy()) return # 小於0不用繼續往下扣找 if remain < 0: return for i in range(start_index, len(candidates)): combination.append(candidates[i]) # 自己可以重複(start_index) backtracking(remain - candidates[i], combination, i) # 如果都回傳完了(不管是否有append到res都會回傳) # 那就繼續下一個i的組合 combination.pop() backtracking(target, [], 0) return res ``` --- **:warning: 錯誤語法** :::warning ::: **:thumbsup:學習** :::success 若在函式中return後面沒有接東西，意思是：結束函式，因為沒有定義資料，所以回傳 None 一般 copy 三種方法 ```python b = list(a) b = a[:] b = a.copy() ``` ::: **思路** **講解連結** https://www.youtube.com/watch?v=GBKI9VSKdGg https://ithelp.ithome.com.tw/articles/10286451 https://www.youtube.com/watch?v=7gcM8zyPtU4&ab_channel=Peter%E5%88%B7Leetcode Provided by. NeetCode ###### tags: `dynamic programming` `medium` `leetcode`