给定一个无重复元素的数组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,
时间: 2024-02-16 13:59:47 浏览: 132
这是一个组合问题,可以使用回溯算法求解。下面是一个基于回溯算法的Python3代码实现:
```python
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
n = len(candidates)
def backtrack(start, tmp_sum, tmp):
if tmp_sum > target:
return
if tmp_sum == target:
res.append(tmp[:])
return
for i in range(start, n):
tmp.append(candidates[i])
backtrack(i, tmp_sum+candidates[i], tmp)
tmp.pop()
backtrack(0, 0, [])
return res
```
其中,回溯函数 `backtrack` 的三个参数分别为:
- `start`:当前可选择的起始元素下标。
- `tmp_sum`:当前已选元素的和。
- `tmp`:当前已选元素组成的列表。
具体实现过程如下:
1. 如果当前已选元素的和 `tmp_sum` 大于目标数 `target`,直接返回。
2. 如果当前已选元素的和 `tmp_sum` 等于目标数 `target`,将 `tmp` 列表加入到结果列表 `res` 中,返回。
3. 从 `start` 开始循环遍历 `candidates` 数组。
4. 将当前遍历到的元素加入到 `tmp` 列表中。
5. 递归调用 `backtrack` 函数,更新 `start` 为当前遍历到的元素下标,更新 `tmp_sum` 为加上当前元素的和,更新 `tmp` 为当前已选元素组成的列表。
6. 将当前遍历到的元素从 `tmp` 列表中弹出,进入下一次循环遍历。
最后,返回结果列表 `res` 即可。
阅读全文