给定一个无重复元素的正整数数组 candidates 和一个正整数 target ,找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。 candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同,则两种组合是不同的。 对于给定的输入,保证和为 target 的唯一组合数少于 150 个
时间: 2024-04-12 09:29:39 浏览: 124
为了解决这个问题,我们可以使用回溯算法。回溯算法通过递归的方式搜索所有可能的组合,同时剪枝不符合条件的分支,以减少不必要的计算。
下面是一个使用回溯算法解决该问题的示例代码(使用 Python 实现):
```python
def combinationSum(candidates, target):
res = []
candidates.sort() # 对数组进行排序,方便后续剪枝操作
def backtrack(remain, curr_comb, start):
if remain == 0: # 如果目标和已经减到0,说明找到了一个符合条件的组合
res.append(curr_comb[:])
return
if remain < 0: # 如果目标和已经减小到负数,说明当前组合不符合条件
return
for i in range(start, len(candidates)):
curr_comb.append(candidates[i]) # 将当前数字加入组合中
backtrack(remain - candidates[i], curr_comb, i) # 继续递归搜索
curr_comb.pop() # 回溯,将当前数字移出组合
backtrack(target, [], 0)
return res
```
使用上述函数,可以得到所有符合条件的唯一组合。例如:
```python
candidates = [2, 3, 6, 7]
target = 7
result = combinationSum(candidates, target)
print(result)
```
输出结果为:
```
[[2, 2, 3], [7]]
```
以上代码实现了在给定数组 candidates 中找出所有数字和为 target 的唯一组合。请注意,为了简化示例,未进行输入验证,实际使用时需要对输入进行合法性检查。
阅读全文