---
# System prepended metadata

title: '**Leetcode筆記(Combination Sum)**'
tags: [medium, microsoft, dynamic programming, leetcode]

---

# **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`