# 39. Combination Sum

{% hint style="success" %}
permutation 来做，一定要有index，下次迭代时用的是`index`而不是`(index+1)`，记录`sum`或者每次都调用`sum()`

最重要的是如何避免重复！！！
{% endhint %}

{% tabs %}
{% tab title="Python" %}

```python
class Solution:
    def helper(self, candidates, target, level, result, index, s):
        # stop condition
        if s > target:
            return
        elif s == target:
            result.append(level[:])
            return
        
        # regular case
        for i in range(index, len(candidates)):
            level.append(candidates[i])
            s = s + candidates[i]
            self.helper(candidates, target, level, result, i, s)
            level.pop()
            s = s - candidates[i]
        
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # edge case
        result = []
        level = []
        if len(candidates) == 0:
            return result
        
        # regular case
        self.helper(candidates, target, level, result, 0, 0)
        return result
```

{% endtab %}

{% tab title="Python3" %}

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        sub = []
        self.helper(candidates, target, sub, 0, result)
        return result
    
    def helper(self, s, target, sub, x, result):
        
        # stop condition
        if target == 0:
            result.append(sub[:])
            return
        elif target < 0:
            return
        
        # regular case
        for i in range(x, len(s)):
            sub.append(s[i])
            self.helper(s, target-s[i], sub, i, result)
            sub.pop()
```

{% endtab %}
{% endtabs %}