C++でちょうどk個の要素を持つすべての部分集合を生成する方法

この記事では、与えられた文字の集合からちょうどk個の要素を含むすべての部分集合（組み合わせ）を生成するC++プログラムを紹介します。再帰によるバックトラッキングを用いることで、指定した長さの組み合わせを漏れなく列挙できます。

アルゴリズム

このアルゴリズムの考え方はシンプルです。各要素について「部分集合に含める」か「含めない」かの2つの選択肢を順に試します。現在の部分集合の要素数（currLen）が要求された長さ（reqLen）に達した時点で、その組み合わせを出力します。

Begin
    function PossibleSubSet(char a[], int reqLen, int s, int currLen, bool check[], int l)
    If currLen > reqLen
        Return
    Else if currLen = reqLen
        新しく生成された組み合わせを出力する
    If s = l
        選べる要素が残っていないため Return
    各インデックスには2つの選択肢がある:
        start を「true」として進め、currLen と s を1ずつ増やして PossibleSubSet() を再帰呼び出しする
        または start を「false」として進め、s のみを1増やして PossibleSubSet() を再帰呼び出しする
End

サンプルコード

#include<iostream>
using namespace std;

// 与えられた配列から要求された長さのすべての組み合わせを出力する関数
void PossibleSubSet(char a[], int reqLen, int s, int currLen, bool check[], int l) {
    if (currLen > reqLen)
        return;
    else if (currLen == reqLen) {
        cout << "\t";
        for (int i = 0; i < l; i++) {
            if (check[i] == true) {
                cout << a[i] << " ";
            }
        }
        cout << "\n";
        return;
    }
    if (s == l) {
        return;
    }
    check[s] = true;
    // 要素を選択する場合：currLen と s を増やして再帰呼び出し
    PossibleSubSet(a, reqLen, s + 1, currLen + 1, check, l);
    check[s] = false;
    // 要素を選択しない場合：s のみを増やして再帰呼び出し
    PossibleSubSet(a, reqLen, s + 1, currLen, check, l);
}

int main() {
    int i, n, m;
    cout << "要素の数を入力してください: ";
    cin >> n;
    bool* check = new bool[n];
    char* a = new char[n];
    cout << "\n";
    for (i = 0; i < n; i++) {
        cout << i + 1 << " 番目の要素を入力してください: ";
        cin >> a[i];
        check[i] = false;
    }
    cout << "\n必要な部分集合の長さを入力してください: ";
    cin >> m;
    cout << "\n長さ " << m << " の組み合わせ一覧:\n";
    PossibleSubSet(a, m, 0, 0, check, n);
    delete[] check;
    delete[] a;
    return 0;
}

実行結果

要素の数を入力してください: 7
1 番目の要素を入力してください: 7
2 番目の要素を入力してください: 6
3 番目の要素を入力してください: 5
4 番目の要素を入力してください: 4
5 番目の要素を入力してください: 3
6 番目の要素を入力してください: 2
7 番目の要素を入力してください: 1

必要な部分集合の長さを入力してください: 6

長さ 6 の組み合わせ一覧:
7 6 5 4 3 2
7 6 5 4 3 1
7 6 5 4 2 1
7 6 5 3 2 1
7 6 4 3 2 1
7 5 4 3 2 1
6 5 4 3 2 1

解説

このプログラムでは、bool型の配列 check[] が「各要素を部分集合に含めるかどうか」を示すフラグとして機能します。再帰の各段階で、現在注目している要素を「選ぶ」経路と「選ばない」経路の両方を探索することで、すべての組み合わせを網羅的に生成します。

計算量は生成される組み合わせの総数に比例し、最悪の場合 O(2ⁿ) となります。そのため、要素数が多くなると実行時間が急激に増加する点に注意が必要です。