Pythonでの組み合わせの合計

候補番号のセット（すべての要素が一意）とターゲット番号があるとします。候補者の数が特定のターゲットに合計される候補者のすべての一意の組み合わせを見つける必要があります。同じ繰り返し数を候補者から無制限に選択することができます。したがって、要素が[2,3,6,7]で、ターゲット値が7の場合、可能な出力は[[7]、[2,2,3]]

手順を見てみましょう-

• これを再帰的に解決します。再帰関数の名前はsolve（）です。これには、結果を格納するための配列、レコードを保持するための1つのマップ、ターゲット値、および個別の要素のリストが必要です。最初はres配列で、マップは空です。解決方法は次のように機能します-

• ターゲットが0の場合、
  • temp：=リストに存在する要素のリスト
  • temp1：=temp、次にtempを並べ替える
  • tempがマップにない場合は、tempをマップに挿入し、値を1に設定して、tempをresに挿入します
  • 戻る
  • temp <0の場合は、戻ります
  • iから要素リストの長さまでの範囲のxの場合、
    • 要素[x]を現在の要素に挿入
    • resolve（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]]