数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究Python中的组合求和
假设我们有一组候选数字（所有元素都是唯一的）和一个目标数字。我们必须找到候选者中所有唯一的组合，其中候选数字之和等于给定的目标。相同的重复数字可以从候选者中无限次选择。因此，如果元素是[2,3,6,7]，目标值为7，则可能的输出将是[[7], [2,2,3]]
让我们看看步骤：
我们将以递归的方式解决这个问题。递归函数名为solve()。它接收一个数组来存储结果，一个映射来保存记录，目标值和一个不同的元素列表。最初，res数组和映射为空。solve方法的工作方式如下：
- 如果目标为0，则
- temp := 列表中存在的元素列表
- temp1 := temp，然后对temp排序
- 如果映射中不存在temp，则将temp插入映射并将其值设置为1，将temp插入res
- 返回
- 如果temp < 0，则返回
- 对于范围从i到元素列表长度的x，
- 将elements[x]插入当前
- solve(elements, target – elements[x], res, map, i, current)
- 从当前列表中删除索引为（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]]
更新于：2020年5月4日
2K+ 浏览量
广告