给定一个无重复元素的数组 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()
仅作为代码记录,方便自学自查自纠