# 39. Combination Sum
#### Difficulty: Medium
link: https://leetcode.com/problems/combination-sum/

### 1. Backtracking
#### $O(n^m)$ runtime, $O(n^m)$ space
###### n = len(candidates), m = target / min(candidates)

### 走法1
result紀錄最終的答案，path紀錄走過的路徑，start_index代表從candidates的哪個index開始往後檢查，value則是還差多少值就達到target。

每次backtracking會判斷下一個要拿哪個candidate，由於candidates已經先將數字從小到大排序好，如果超過需要達成的value還能early stop。
##### python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result = []
        def backtracking(path, start_index, value):
            for i in range(start_index, len(candidates)):
                cand = candidates[i]
                if cand < value:
                    backtracking(path + [cand], i, value - cand)
                elif cand == value:
                    result.append(path + [cand])
                else:
                    break
        
        backtracking([], 0, target)
        return result

### 走法2
backtrack每次選擇要或不要拿now_idx這個的元素，如果不拿就往下一個元素看，如果拿就繼續待在同一個元素。
##### python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        def backtrack(now_ans, now_idx, now_target):
            if now_target == 0:
                ans.append(now_ans)
                return
            
            if now_idx == len(candidates) or now_target < 0:
                return
            
            backtrack(now_ans+[candidates[now_idx]], now_idx, now_target-candidates[now_idx])
            backtrack(now_ans, now_idx+1, now_target)
        
        backtrack([], 0, target)

        return ans

###### tags: `leetcode`