# [LeetCode] 39. Combination Sum (Medium)

###### tags: `LeetCode`

## 題目
給定一串排序好的正整數`candidates`，以及一個目標正整數`target`，回傳所有由`candidates`裡面的數組成、加起來為`target`的組合，其中單個數字可以重複出現。

## 限制條件
* `1 <= candidates.length <= 30`
* `1 <= candidates[i] <= 200`
* `candidates`中的元素不重複
* `1 <= target <= 500`

## 範例
* Example 1:

    輸入: candidates = [2,3,6,7], target = 7
    輸出: [[2,2,3],[7]]

`2 + 2 + 3 = 7`。注意這邊`2`可以不只出現一次。`7`在`candidates`裡面，而`7 = 7`，所以總共有2種組合。

* Example 2:

    輸入: candidates = [2,3,5], target = 8
    輸出: [[2,2,2,2],[2,3,3],[3,5]]

* Example 3:

    輸入: candidates = [2], target = 1
    輸出: []

## 解答
### 思路
這題可以使用backtracking（回溯）的技巧來解決。聽起來很厲害，但其實只是模仿人腦在解決這種問題的思路而已。

假設現在的`candidates = [3, 4, 5]`，`target = 8`。我們可以把問題轉換成以下形式：
> 你身上帶了8塊錢，現在有三種商品，一種3塊錢、一種4塊錢，還有一種5塊錢。每種商品可以重複購買、也可以不購買，那麼有哪些購買方式可以把錢花光？

從空的購物籃開始，可以選擇先放入3塊錢、4塊錢或5塊錢的物品，並接著採取相應的行動：
* 如果第一個放入的是3塊錢的物品，第二個放入的物品可以選擇3塊錢、4塊錢或5塊錢的物品。
* 如果第一個放入的是4塊錢的物品，第二個放入的物品可以4塊錢或5塊錢的物品。如果第二個放入的物品是3塊錢的物品，則會和前面考慮的情況重複了。
* 如果第一個放入的是5塊錢的物品，第二個放入的物品只能是5塊錢的物品，理由同上。

按照這樣的邏輯，可以畫出一棵樹來表示可以採取的行動：

那麼如果爆掉了，也就是走到圖中的紅色節點，該怎麼辦呢？這時候我們可以沿著原路「回溯」，直到找到其他可行的路為止。

### 演算法
在這邊我們定義一個遞迴函式`backtrack(remain, comb, start)`來產生題目要求的組合：從`comb`開始，目標是完成`remain`的購買組合，而`start`則是這個購買組合中價格最低的商品在`candidates`的index。

在這裡我們考慮兩個 base case：
* `remain = 0`：這時候的組合`comb`加起來剛好滿足`target`，故可以把`comb` append 在`result`上。注意在這邊我們 append 的是`comb.copy()`而不是直接 append `comb`，這是因為如果直接直接 append `comb`的話，後續對`comb`的修改也會影響到`result`。
* `remain < 0`：這時候的組合`comb`加起來超過`target`了，這條路不能再走下去。

接著考慮 recursive case：`remain > 0`。根據前面的討論，我們只需要考慮`candidates[start:]`這個sublist，對裡面的每個元素進行迭代，進行以下操作：
* 把目前的元素`candidates[i]` append 到`comb`裡面。
* 因為加入了元素，`remain`減少了`candidates[i]`，所以我們呼叫`backtrack(remain - candidates[i], comb, i)`
* 完成每一次迭代時，把最後一個元素 pop 出來以達成backtrack。

這個問題可以看作是一棵 n-ary tree 的尋訪（traversal）問題，尋訪的就是剛剛畫出的那棵樹，而解題的思路事實上就是一個DFS的過程。

### Code

class Solution:
    def combinationSum(self, cands: List[int], target: int) -> List[List[int]]:
        result = []
        
        def backtrack(remain, comb, start):
            if remain == 0:
                result.append(comb.copy())
                return
            elif remain < 0:
                return 
            for i in range(start, len(cands)):
                comb.append(cands[i])
                backtrack(remain - cands[i], comb, i)
                comb.pop()
        
        backtrack(target, [], 0)
        
        return result

### 複雜度
假設：
* $N$ 為`candidates`的總數
* $T$ 為`target`的值
* $M$ 為`candidates`裡面最小的值

> 時間複雜度：$O\left(N^{\frac{T}{M} + 1}\right)$

在一個graph上進行DFS的複雜度就是整個graph的vertex數，所以我們現在必須來估計這棵樹上有幾個節點：
* 每個節點的分支度為 $O(N)$
* 樹的高度為 $O(T/M + 1)$

我們知道一棵樹的節點數量可以用$O(分支度^{高度})$ 來估計，因此時間複雜度為 $O\left(N^{\frac{T}{M} + 1}\right)$。

> 空間複雜度：$O\left(\frac{T}{M}\right)$

在這邊，空間複雜度和遞迴函數呼叫的 stack 大小有關，這個 stack 的大小為 $O\left(\frac{T}{M}\right)$。另一方面，我們需要一個 list of list 來儲存解答需要的組合，大小也是 $O\left(\frac{T}{M}\right)$。所以總共加起來，空間複雜度仍然是 $O\left(\frac{T}{M}\right)$。