C#で指定した数値の合計になる一意な組み合わせを見つける方法

C#ではバックトラッキング（Backtracking）の手法を用いることで、指定した数値の合計になる一意な数字の組み合わせを効率的に求めることができます。この記事では、その考え方と具体的な実装例をわかりやすく解説します。

アルゴリズムの基本的な考え方

まず、有効な組み合わせを格納するための出力リストと、再帰探索の途中経路で見つかった現在の組み合わせを保持する現在リストを用意します。そして、目標値に達するまで再帰的に探索を進めるバックトラック関数を実装します。合計が目標値を超えた時点で、それ以上探索を続けても有効な解は得られないため、直前の状態に戻る（バックトラックする）のがポイントです。

具体的な処理の流れは以下のとおりです。

1. 合計が目標値と一致した場合：現在のリストを出力リストに追加します。このとき、候補配列内の値の合計がちょうど目標値に等しくなっているためです。
2. 合計が目標値を超えた場合：これ以上探索を続けても意味がないため、前の段階へ戻ります。
3. どちらでもない場合：候補配列の要素を1つずつ現在のリストに追加しながら、再帰的に探索を進めます。

例として、対象の数値が「5」である場合を考えてみましょう。この場合、合計が5になる数字の組み合わせを求めることになります。答えは「1+4」「2+3」「5」の3パターンです。

サンプルコード

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
   public class BackTracking{
      public void UniqueCombinationOfNumbersCorrespondsToSum(int n){
         int[] array = new int[n + 1];
         for (int i = 1; i <= n; i++){
            array[i] = i;
         }
         List<int> currentList = new List<int>();
         List<List<int>> output = new List<List<int>>();
         UniqueCombinationSum(array, n, 0, 0, currentList, output);
         foreach (var item in output){
            StringBuilder s = new StringBuilder();
            foreach (var item1 in item){
               s.Append(item1.ToString());
            }
            Console.WriteLine(s);
            s = null;
         }
      }
      private void UniqueCombinationSum(int[] array, int target, int sum, int index, List<int> currentList, List<List<int>> output){
         if (sum == target){
            List<int> newList = new List<int>();
            newList.AddRange(currentList);
            output.Add(newList);
            return;
         }
         else if (sum > target){
            return;
         }
         else{
            for (int i = index; i < array.Length; i++){
               currentList.Add(array[i]);
               UniqueCombinationSum(array, target, sum + array[i], i + 1, currentList, output);
               currentList.Remove(array[i]);
            }
         }
      }
   }
   class Program{
      static void Main(string[] args){
         BackTracking b = new BackTracking();
         b.UniqueCombinationOfNumbersCorrespondsToSum(5);
      }
   }
}

実行結果

14
23
5

このようにバックトラッキングを活用すれば、重複のない組み合わせだけを網羅的に列挙できます。特に、再帰呼び出し時に探索開始位置（index）を渡すことで、同じ要素の並び替えによる重複を防いでいる点が、この実装の重要なポイントです。