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+ 浏览量

开启你的职业生涯

完成课程获得认证

开始学习
广告