39 Combination Sum

candidates 数组中没有重复的数字，但是combination中各个数字可以使用多次, 注意为了避免得到的集合中出现重复的组合，使用backtracking 进行解决

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        ans = []

        def dfs(index, cur, cur_set):
            if cur == target:
                ans.append(cur_set)
                return
            if cur > target:
                return
            length = len(candidates)
            for i in range(index, length):
                new_set = cur_set[:]
                new_set.append(candidates[i])
                dfs(i, cur + candidates[i], new_set)

        dfs(0, 0, [])
        return ans