Python中的组合和

假设我们有一组候选编号（所有元素都是唯一的）和一个目标编号。我们必须在候选者中找到所有唯一组合，其中候选者数字之和等于给定目标。可以从候选人无限制的次数中选择相同的重复数。因此，如果元素为[2,3,6,7]并且目标值为7，则可能的输出将为[[7]，[2,2,3]]

让我们看看步骤-

• 我们将以递归方式解决此问题。递归函数名为solve()。这需要一个数组来存储结果，一个映射来保存记录，目标值和一系列不同的元素。最初res数组和map为空。解决方法将如下所示工作-

• 如果目标为0，则

• 将elements [x]插入当前

• resolve（元素，目标–元素[x]，res，映射，i，当前）

• 从索引中删除当前列表中的元素（当前长度– 1）

• temp：=列表中存在的元素的列表

• temp1：= temp，然后排序temp

• 如果temp不在映射中，则将temp插入映射并将值设置为1，将temp插入res

• 返回

• 如果temp <0，则返回

• 对于范围i到元素列表长度的x，

让我们看下面的实现以更好地理解-

示例

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]]