2.用递归实现如下问题:给定一个数组nums=[2,3,5]和一个固定的值target=8。找出数组nums中所有可以使数字和为target的组合(数字可重复)。
时间: 2023-04-30 07:06:57 浏览: 91
这个问题可以通过回溯算法来解决。首先定义一个helper函数来进行回溯,函数需要三个参数:目前遍历到的位置index、已经计算出的当前和current_sum、以及当前的结果集合subsets。如果当前和等于target,把当前结果加入subsets中,如果当前和超出了target,就不再继续搜索。最后返回subsets即可。
具体实现可以参考下面的代码:
```
class Solution:
def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
res = []
def helper(start, current_sum, subset):
if current_sum == target:
res.append(subset)
elif current_sum > target:
return
else:
for i in range(start, len(nums)):
helper(i, current_sum + nums[i], subset + [nums[i]])
helper(0, 0, [])
return res
```
我们通过传入一个空集合作为初始结果集合,然后调用helper函数进行回溯,最后返回结果即可。
阅读全文