python代码给定一个**无重复元素**的数组 candidates 和一个目标数 target , 找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
时间: 2024-09-09 14:12:28 浏览: 50
java代码-给出一组候选数\ C C 和一个目标数\ T T,找出候选数中起来和等于\ T T 的所有组合。 \ C C 中的每个数字在一个组合中只能使用一次
在Python中,解决这个问题通常会采用回溯法(Backtracking)。你可以创建一个函数,它接受当前的目标值、剩余候选列表以及已经选择过的数字列表作为输入。当目标值等于0时,说明找到了一组解;如果目标值小于0,则回溯并尝试下一个候选数。以下是简单的代码示例:
```python
def combinationSum(candidates, target):
def backtrack(start, current_sum, chosen):
# 如果目标值达到0,添加当前组合到结果集中
if current_sum == target:
result.append(chosen)
return
# 遍历剩余的候选数
for i in range(start, len(candidates)):
# 如果候选数已经在选择中,跳过
if i > start and candidates[i] == candidates[i - 1]:
continue
# 尝试加入当前数到组合
backtrack(i + 1, current_sum + candidates[i], chosen + [candidates[i]])
result = []
candidates.sort() # 对候选数组排序,避免重复计数
backtrack(0, 0, [])
return result
# 示例
candidates = [2, 3, 6, 7]
target = 7
print(combinationSum(candidates, target)) # 输出:[[2, 2, 3], [7]]
```
这个代码首先对候选数组排序,然后从第一个数开始进行回溯。如果当前数已经是选择过的,就跳过;否则,尝试将其加入到当前的解决方案中,并继续寻找其他可能的组合。
阅读全文