39. Combination Sum

"""
39. Combination Sum
这道题是一道很典型的backtrack的题。backtrack写起来首先就是要写出来return的条件，
1. 当违反递归规则时，直接return。
2. 当符合递归规则时，将求解写到result中。
然后执行递归。
注意递归时的传入参数
"""

class Solution(object):
    def backtrack(self, ls, idx, tmp, val, res):
        if val < 0:
            return

        if val == 0:
            res.append(tmp)
            return

        for i in range(idx, len(ls)):
            self.backtrack(ls, i, tmp + [ls[i]], val - ls[i], res)

        return

    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()

        self.backtrack(candidates, 0, [], target, res)

        return res