39. 组合总和

https://leetcode.cn/problems/combination-sum/

补上一个组合总数

思路：

• 回溯
• 维护rest作为还差多少到target的值
• 重点是去重，由于每个数字都可以重复，所以startIndex可以从当前位置开始，但不可以选取之前的数，从而达到去重的目的

没什么难度，hint：遇到回溯画个图，一个图不行，就画两个图

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        n = len(candidates)
        def backtracking(path, rest, startIndex):
            if rest < 0:
                return
            if rest == 0:
                ans.append(path[:])
                return
            for i in range(startIndex, n):
                path.append(candidates[i])
                backtracking(path, rest - candidates[i], i)
                path.pop()
        backtracking([], target, 0)
        return ans