C#のバックトラッキングで配列から目標合計となる組み合わせを見つける方法

目標合計問題（Target Sum Problem）とは

目標合計問題とは、与えられた配列の中から要素を組み合わせて選んだとき、その要素の合計が指定した数値（目標値）と一致するような組み合わせを見つける問題です。

バックトラッキング（バックトラック法）によるアプローチでは、最悪の場合すべての組み合わせを探索することになりますが、それでも一般には部分和問題に対する単純な再帰アプローチよりも効率的に動作します。途中で合計が目標値を超えた時点でその経路を打ち切る「枝刈り」ができるためです。

ここでは、n個の正整数からなる配列と目標値 sum が与えられたとき、配列の要素は何度でも繰り返し使用できるものとして、合計が sum と一致するすべての組み合わせを求めます。

具体例

たとえば、配列 [1, 2, 3]、目標値 4 を与えると、次のような出力が得られます。

• "1111"
• "112"
• "13"
• "22"

このとき、"31" や "211"、"121" のように並び順だけが異なる重複結果は除外されます。再帰呼び出しの際に現在のインデックスを引き継ぎ、そのインデックス以降の要素だけを候補にすることで、順列の重複が自動的に排除される仕組みです。

C#での実装例

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication {
   public class BackTracking {
      public void Combinationsums(int[] array, int target) {
         List<int> currentList = new List<int>();
         List<List<int>> results = new List<List<int>>();
         int sum = 0;
         int index = 0;

         CombinationSum(array, target, currentList, results, sum, index);

         foreach (var item in results) {
            StringBuilder s = new StringBuilder();
            foreach (var item1 in item) {
               s.Append(item1.ToString());
            }
            Console.WriteLine(s);
         }
      }

      private void CombinationSum(int[] array, int target,
         List<int> currentList, List<List<int>> results,
         int sum, int index) {

         // 合計が目標値を超えたら探索を打ち切る（枝刈り）
         if (sum > target) {
            return;
         }
         // 合計が目標値と一致したら結果として保存
         else if (sum == target) {
            List<int> newList = new List<int>();
            newList.AddRange(currentList);
            results.Add(newList);
            return;
         }
         else {
            // 現在のインデックス以降の要素だけを候補にする
            for (int i = index; i < array.Length; i++) {
               currentList.Add(array[i]);
               CombinationSum(array, target, currentList,
                  results, sum + array[i], i);
               // 選択を取り消して元の状態に戻す（バックトラック）
               currentList.Remove(array[i]);
            }
         }
      }
   }

   class Program {
      static void Main(string[] args) {
         BackTracking b = new BackTracking();
         int[] arrs = { 1, 2, 3 };
         b.Combinationsums(arrs, 4);
      }
   }
}

実行結果

1111
112
13
22

コードのポイント

• 枝刈り： 合計 sum が目標値 target を超えた瞬間に再帰を打ち切るため、無駄な探索が発生しません。
• 重複の防止： 再帰呼び出しに現在のインデックス i を渡し、ループもそのインデックスから開始することで、"13" と "31" のような順番違いの重複組み合わせが生成されなくなります。
• バックトラッキング： 要素を currentList に追加して再帰的に探索した後、Remove で取り除いて状態を元に戻します。これにより、次の候補を使った別の経路の探索が可能になります。

このように、バックトラッキングを活用することで、配列の要素を繰り返し使用しながら、目標合計となるすべての組み合わせを効率的に列挙できます。