[leetcode]39_组合总和_给定数组且数组可重复

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为： [ [7], [2,2,3] ]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]

解题思路：【回溯】

迭代三部曲：1、确认递归函数返回值与参数：candidates,targetSum,结果数组res，子集合path，子集合首元素起始位置startindex2、回溯函数终止条件：子集合和 = targetSum则回溯寻找下一组子集3、单层搜索过程：循环遍历[startindex, len(candidates)]的每个元素i剪枝：sum(path) > n，则直接回溯寻找子集下一个元素path.append(candidates[i])，再递归寻找子集合下一元素，仍然从i寻找（可重复）；若子集合的遍历终止，则回溯path.pop()，遍历下一个元素i + 1。

import traceback
class Solution:def combination_total(self, candidates, targetSum, res, startindex, path=[]):length = len(path)if sum(path) == targetSum:res.append(path[:])#   回溯，寻找下一组returnfor i in range(startindex, len(candidates)):#   剪枝，若加入当前元素candidates[i] > targetSum，则不对candidates[i]进行操作if sum(path) + candidates[i] > targetSum:continuepath.append(candidates[i])self.combination_total(candidates, targetSum, res, i, path)#   回溯path.pop()if __name__ == '__main__':try:# candidates = list(map(int, input().split(',')))candidates = eval(input())targetSum = int(input())res = []solution = Solution()solution.combination_total(candidates, targetSum, res, 0)print(res)except Exception as e:traceback.print_exc()

仅作为代码记录，方便自学自查自纠