###### tags: `Leetcode` `medium` `array` `backtracking` `python` `Top 100 Liked Questions`

# 39. Combination Sum

## [題目連結:] https://leetcode.com/problems/combination-sum/

## 題目:
Given an array of **distinct** integers ```candidates``` and a target integer ```target```, return a list of all **unique combinations** of ```candidates``` where the chosen numbers sum to ```target```. You may return the combinations in **any order**.

The **same** number may be chosen from ```candidates``` an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is **guaranteed** that the number of unique combinations that sum up to ```target``` is less than ```150``` combinations for the given input.

**Example 1:**

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

**Example 2:**

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

**Example 3:**

Input: candidates = [2], target = 1
Output: []

## 解題想法:
兄弟題目: [40. Combination Sum II](/YxlQmfbsRV2-hX7xVVdtiw)
* 題目要求，給一數組，return所有能和為target的組合，
* 每個數能用任意次數
* 組合不能重複
* 先將數組進行排序，必免後續順序問題
* 當目前和==target
* 將此組合加入最終ans
* 逐一遍歷數組，
* 當目前數為val時候
* 看目前path中最後一個數(為當前path最大的)
* 只能選與path[-1]相等or更大的val進行下個遞迴

## Python:

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        #先將數進行排序
        #這樣取值時 後面數需大於等於前面的數 以避免組合重複
        self.ans = []
        candidates.sort()
        self.dfs(target,candidates,[])
        return self.ans
    
    def dfs(self,cur_target,candidates,path):
        if cur_target==0:
            self.ans.append(path)
        for value in candidates:
            #若大於 後面也不用找了
            if value>cur_target:
                break
            #去除重複順序問題
            #ex:candidates為[2,3,4,5,6]
            #該path已為[2,2,3,4]，則再往後遞迴只能用4、5、6來check
            if path and value<path[-1]:
                continue
            self.dfs(cur_target-value,candidates,path+[value])
            
if __name__ == '__main__':
    result = Solution()
    candidates = [2,3,5]
    target = 8
    ans = result.combinationSum(candidates,target)
    print(ans)