Python 中的组合总和
pythonserver side programmingprogramming更新于 2025/11/18 22:36:17
假设我们有一组候选数字(所有元素都是唯一的)和一个目标数字。我们必须在候选数字中找到所有唯一组合，使候选数字的总和等于给定的目标。可以从候选数字中选择相同的重复数字，次数不限。因此，如果元素为 [2,3,6,7] 且目标值为 7，则可能的输出为 [[7], [2,2,3]]
让我们看看步骤 −
我们将以递归方式解决此问题。递归函数名为solve()。它需要一个数组来存储结果，一个映射来保存记录，目标值和一个不同元素的列表。最初，res 数组和映射为空。解决方法将像下面这样工作 −
- 如果 target 为 0，则
- temp := 列表中存在的元素列表
- temp1 := temp，然后对 temp 进行排序
- 如果 temp 不在 map 中，则将 temp 插入 map 并将值设置为 1，将 temp 插入 res
- 返回
- 如果 temp < 0，则返回
- 对于范围 i 到元素列表长度内的 x，
- 将 elements[x] 插入当前
- solve(elements, target – elements[x], res, map, i, current)
- 从索引(当前长度 – 1)中删除当前列表中的元素
让我们看看下面的实现以便更好地理解 −
示例
class Solution(object):
def combinationSum(self, candidates, target):
result = []
unique={}
candidates = list(set(candidates))
self.solve(candidates,target,result,unique)
return result
def solve(self,candidates,target,result,unique,i = 0,current=[]):
if target == 0:
temp = [i for i in current]
temp1 = temp
temp.sort()
temp = tuple(temp)
if temp not in unique:
unique[temp] = 1
result.append(temp1)
return
if target <0:
return
for x in range(i,len(candidates)):
current.append(candidates[x])
self.solve(candidates,target-candidates[x],result,unique,i,current)
current.pop(len(current)-1)
ob1 = Solution()
print(ob1.combinationSum([2,3,6,7,8],10))
输入
[2,3,6,7,8] 10
输出
[[2, 8], [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [3, 7]]
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
