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:returnif sum == target:result.append(path[:])returnfor 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 resultdef 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:returnif sum == target:result.append(path[:])returnfor i in range(startIdx, len(candidates)):if candidates[i] == candidates[i-1]:passpath.append(candidates[i])sum += candidates[i]self.traversal(result, path, sum, i, candidates, target)path.pop()sum -= candidates[i]return resultdef combinationSum(self, candidates, target):result = []path = []return self.traversal(result, path, 0, 0, candidates, target)