Pythonで組み合わせの総和（Combination Sum）を求める再帰アルゴリズムの解説

組み合わせの総和問題とは

候補となる数値のリスト（すべての要素が一意）と目標値が与えられたとき、候補の数値を足し合わせて目標値と一致する、すべての一意な組み合わせを求めるのが「組み合わせの総和」問題です。このとき、同じ数値は何度でも繰り返し使用できる点が特徴です。

たとえば、要素が [2,3,6,7] で目標値が 7 の場合、考えられる出力は [[7], [2,2,3]] となります。

解法のアプローチ

この問題は再帰処理によって解きます。再帰関数 solve() は、結果を保存する配列（res）、重複チェック用の辞書（map）、目標値（target）、そして一意な要素のリスト（elements）を受け取ります。初期状態では res と map は空です。solve メソッドの動作は以下の通りです。

• target が 0 の場合：
  • current リスト内の要素からリスト temp を作成する
  • temp1 := temp のコピーを作成し、temp をソートしてタプル化する
  • temp が map に存在しなければ、map[temp] = 1 を登録し、temp1 を res に追加する
  • return で終了する
• target が負の場合： return で終了し、その経路の探索を打ち切る
• それ以外の場合： インデックス i から elements の長さまでループし、以下を繰り返す
  • elements[x] を current に追加する
  • solve(elements, target − elements[x], res, map, i, current) を再帰呼び出しする
  • current の末尾から要素を削除し、状態を元に戻す（バックトラック）

実装例

以下のコードで実際の動作を確認できます。

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

コードのポイント

• set() を使って候補リストから重複要素を事前に除去しています。
• current.pop(...) によるバックトラックで、探索木の各分岐を正しく元の状態に戻しています。
• unique 辞書を活用することで、ソート済みの組み合わせをキーとして管理し、同じ組み合わせが結果に複数回含まれるのを防止しています。
• 再帰呼び出し時に開始インデックス i を引き継ぐことで、順序が異なるだけの同一組み合わせ（例： [2,3,3] と [3,2,3]）の無駄な生成を抑えています。