代码随想录算法训练营第二十六天（回溯算法篇）|39. 组合总和，40. 组合总和Ⅱ

39. 组合总和

题目链接：39. 组合总和 - 力扣（LeetCode）

题目内容：给你一个?无重复元素?的整数数组?candidates?和一个目标整数?target?，找出?candidates?中可以使数字和为目标数?target?的 所有?不同组合?，并以列表形式返回。你可以按?任意顺序?返回这些组合。candidates?中的?同一个?数字可以?无限制重复被选取?。如果至少一个数字的被选数量不同，则两种组合是不同的。?

思路：和之前的组合那道题不同点在于1. if条件不用要求path的长度，只要和相同，就返回，可以加上剪枝——当和大于target，直接返回。2. 递归时的起始值（startIdx）是i，不是i+1, 因为可以重复。

class Solution(object):
    def traversal(self, result, path, sum, startIdx, candidates, target):
        if sum > target:
            return
        if sum == target:
            result.append(path[:])
            return
        for i in range(startIdx, len(candidates)):
            path.append(candidates[i])
            sum += candidates[i]
            self.traversal(result, path, sum, i, candidates, target)
            path.pop()
            sum -= candidates[i]
        return result

    def combinationSum(self, candidates, target):
        result = []
        path = []
        return self.traversal(result, path, 0, 0, candidates, target)

        

40. 组合总和Ⅱ

题目链接：40. 组合总和 II - 力扣（LeetCode）

题目难点：题目里给出的数组有重复元素，但要求答案里不能有重复组合.

思路：我们要对同一数层上重复使用的元素去重——前一个相同的元素要相加的数的范围大于后面那个元素家的范围，所以一定包含后一个元素找到的数。因此，我们可以对candidates进行排序，做for循环时只需判断当前元素和它前一个元素是否相同，若相同，就pass掉，对当前元素不做处理，继续跳到后一个数。

class Solution(object):
    def traversal(self, result, path, sum, startIdx, candidates, target):
        candidates = sorted(candidates)
        if sum > target:
            return
        if sum == target:
            result.append(path[:])
            return
        for i in range(startIdx, len(candidates)):
            if candidates[i] == candidates[i-1]:
                pass
            path.append(candidates[i])
            sum += candidates[i]
            self.traversal(result, path, sum, i, candidates, target)
            path.pop()
            sum -= candidates[i]
        return result

    def combinationSum(self, candidates, target):
        result = []
        path = []
        return self.traversal(result, path, 0, 0, candidates, target)