C#のバックトラッキングで配列から個別のサブセット（組み合わせ）を求める方法

個別のサブセット問題とは

「個別のサブセット問題」では、与えられた配列から重複しない組み合わせをすべて抽出します。目標とする要素数（ターゲット）が2であれば、配列の中から2つの要素を選ぶすべての組み合わせを、ターゲットが3であれば3つの要素を選ぶすべての組み合わせを求めます。

例えば、配列が [1, 2, 3] でターゲットが 2 の場合、取得できる組み合わせは「1,2」「2,3」「1,3」の3つになります。

C#での実装例（バックトラッキング）

以下のコードでは、バックトラッキング（探索の途中で条件を満たさなくなったら一つ前の状態に戻る手法）を使って、指定したサイズの組み合わせを効率的に生成しています。

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

namespace ConsoleApplication
{
    public class BackTracking
    {
        public void Subsets(int[] array)
        {
            List<int> currentList = new List<int>();
            List<string> results = new List<string>();

            // ターゲットサイズを2としてバックトラッキングを開始
            BackTrackingCombination(array, 2, 0, currentList, results);

            foreach (var item in results)
            {
                Console.WriteLine(item);
            }
        }

        public void BackTrackingCombination(int[] array, int size, int startIndex,
                                            List<int> currentList, List<string> results)
        {
            // 現在のリストの要素数がターゲットに達したら結果に追加
            if (currentList.Count == size)
            {
                StringBuilder s = new StringBuilder();
                foreach (var item in currentList)
                {
                    s.Append(item);
                }
                results.Add(s.ToString());
                return;
            }

            // startIndex以降の要素を順に選択して再帰的に組み合わせを生成
            for (int i = startIndex; i < array.Length; i++)
            {
                currentList.Add(array[i]);
                BackTrackingCombination(array, size, i + 1, currentList, results);
                currentList.Remove(array[i]); // バックトラック：選択を取り消す
            }
        }
    }

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

コードのポイント

• currentList： 現在構築中の組み合わせを保持するリストです。
• startIndex： 同じ要素を重複して選ばないよう、次の再帰呼び出しでは現在位置より後ろの要素だけを対象にします。これにより「1,2」と「2,1」のような順序違いの重複を防ぎます。
• バックトラック処理： 再帰呼び出しから戻った後、Remove で直前に追加した要素を取り消し、別の候補を試します。
• 終了条件： currentList.Count == size になった時点で、その組み合わせを文字列化して結果リストに格納します。

実行結果

12
13
23

このように、バックトラッキングを利用すると、配列から指定したサイズの個別のサブセット（組み合わせ）をシンプルかつ体系的に列挙できます。ターゲットの値を変更すれば、任意の要素数の組み合わせにも柔軟に対応できます。