【leetcode100】组合总和

1、标题形貌

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 差别组合 ，并以列表形式返回。你可以按 任意次序 返回这些组合。
candidates 中的 同一个 数字可以 无穷制重复被选取 。假如至少一个数字的被选数量差别，则两种组合是差别的。 
对于给定的输入，保证和为 target 的差别组合数少于 150 个。
示例 1：

1. <strong>输入：</strong>candidates = [2,3,6,7], target = 7
2. <strong>输出：</strong>[[2,2,3],[7]]
3. <strong>解释：</strong>
4. 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
5. 7 也是一个候选， 7 = 7 。
6. 仅有这两种组合。

复制代码

2、初始思路

2.1 思路

本道题中，抽象为树状图为：

2.2 代码

1. class Solution:
2.     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
3.         res = []
4.         path = []
5.         def backtracking(candidates, target, sumCurrent, startIndex):
6.             if sumCurrent > target:
7.                 return
8.             if sumCurrent == target:
9.                 res.append(path.copy())
10.                 return
11.             for i in range(startIndex,len(candidates)):
12.                 path.append(candidates[i])
13.                 sumCurrent += candidates[i]
14.                 backtracking(candidates, target, sumCurrent, i)
15.                 sumCurrent -= candidates[i]
16.                 path.pop()
17.         backtracking(candidates, target, 0, 0)
18.         return res

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。