39. Combination Sum

# Medium

permutation 来做，一定要有index，下次迭代时用的是index而不是(index+1)，记录sum或者每次都调用sum()

最重要的是如何避免重复！！！

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

Python3

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()