C#でバックトラッキングを使って、合計がnになるk個の数値のユニークな組み合わせを求める方法

アルゴリズムの考え方

この問題は、バックトラッキング（探索と巻き戻し）を用いて解くことができます。まず、最終的な答えを格納するための出力リストと、再帰木をたどる過程で現在使用中の数値列を一時的に保持する現在のリストを用意します。

次に、再帰処理を行うバックトラッキング関数を定義します。この関数は、合計値が目標値に達するまで再帰的に探索を進めます。もし合計値が目標値を超えてしまった場合は、それ以上探索を続けても意味がないため、直前の状態へ戻り（バックトラックし）、別の候補を試します。

探索の途中で合計値がちょうど目標値と一致した場合は、選択中の数値の個数がk個に達しているかどうかを確認します。両方の条件を満たしていれば、その時点の候補配列を出力リストに追加します。これにより、「候補となる数値の合計が指定された目標値と一致する」ことが保証されます。

上記のいずれの条件にも当てはまらない場合は、候補配列の要素を1つずつ現在のリストに追加しながら、再帰的に探索を続けていきます。

具体例

例えば、n = 5、k = 2 とします。この場合、「合計が5になる2つの数値の組み合わせ」を求めることになります。結果として得られるのは「1, 4」と「2, 3」の2通りです。

サンプルコード

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
    public class BackTracking{
        public void UniqueCombinationSumOfExactKNumbers(int n, int k){
            int[] array = new int[n];
            for (int i = 1; i < n; i++){
                array[i] = i;
            }
            List<int> currentList = new List<int>();
            List<List<int>> output = new List<List<int>>();
            UniqueCombinationSumOfExactKNumbers(array, n, k, 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 UniqueCombinationSumOfExactKNumbers(int[] array, int target, int countOfNumbers, int sum, int index, List<int> currentList, List<List<int>> output){
            if (sum == target){
                if (currentList.Count == countOfNumbers){
                    List<int> newList = new List<int>();
                    newList.AddRange(currentList);
                    output.Add(newList);
                    return;
                }
            }
            else if (sum > target){
                return;
            }
            else if (currentList.Count == countOfNumbers && sum != target){
                return;
            }
            else{
                for (int i = index; i < array.Length; i++){
                    currentList.Add(array[i]);
                    UniqueCombinationSumOfExactKNumbers(array, target, countOfNumbers, sum + array[i], i + 1, currentList, output);
                    currentList.Remove(array[i]);
                }
            }
        }
    }
    class Program{
        static void Main(string[] args){
            BackTracking b = new BackTracking();
            b.UniqueCombinationSumOfExactKNumbers(5, 2);
        }
    }
}

実行結果

14
23

ポイント解説

• 重複の防止： 再帰呼び出し時に次のインデックス（i + 1）を渡すことで、同じ数値を重複して選択したり、「1,4」と「4,1」のような順序違いの同一組み合わせが複数生成されるのを防いでいます。
• 枝刈りによる効率化： 合計値が目標値を超えた時点で即座にreturnすることで、無駄な探索を打ち切り、全体的な処理効率を高めています。
• 個数チェック： 合計が目標値と一致しても、選んだ数値の個数がk個でなければ結果には追加しません。「ちょうどk個の数値で合計nを作る」という条件を満たすために不可欠な判定です。