C++で配列から指定サイズのすべての部分集合（サブセット）を出力する方法

この記事では、与えられた配列から、指定されたサイズ r のすべての部分集合（サブセット）を生成して出力する方法を解説します。これは組み合わせ（コンビネーション）を求める古典的なアルゴリズム問題の一つです。

問題の概要

要素が n 個含まれる配列が与えられたとき、その配列の要素を使って作れる「サイズ r の組み合わせ」をすべて出力します。同じ組み合わせは一度だけ出力し、重複は除外する点に注意してください。

入力例と出力例

入力：
array = {3, 5, 6}
r = 2

出力：
3 5
3 6
5 6

上記の例では、要素 {3, 5, 6} から 2 個を選ぶ組み合わせは 「{3, 5}」「{3, 6}」「{5, 6}」 の 3 通りになります。

アルゴリズムの考え方

この問題は再帰（バックトラッキング）を用いて解くのが一般的です。基本的なアプローチは以下の通りです。

1. 現在の要素を部分集合に含める場合と含めない場合の、2 つの分岐を作る。
2. 部分集合のサイズが r に達したら、その時点での内容を出力して再帰を終了する。
3. 配列の末尾まで到達したら探索を打ち切る。
4. すでに選んだ組み合わせと同じものは生成されないため、重複チェックは不要です。

C++による実装例

#include <iostream>
using namespace std;

void printSubset(int arr[], int n, int r, int index, int data[], int i);

int main(){
    int arr[] = {3, 5, 6};
    int r = 2;
    cout << "The sets are : ";
    int n = sizeof(arr) / sizeof(arr[0]);
    int data[r];
    printSubset(arr, n, r, 0, data, 0);
    return 0;
}

void printSubset(int arr[], int n, int r, int index, int data[], int i){
    // 部分集合のサイズが r に達したら出力
    if (index == r) {
        for (int j = 0; j < r; j++)
            cout << data[j] << " ";
        cout << endl;
        return;
    }
    // 配列の末尾まで来たら終了
    if (i >= n)
        return;

    // 現在の要素を選ぶ場合
    data[index] = arr[i];
    printSubset(arr, n, r, index + 1, data, i + 1);

    // 現在の要素を選ばない場合
    printSubset(arr, n, r, index, data, i + 1);
}

実行結果

The sets are :
3 5
3 6
5 6

計算量について

n 個の要素から r 個を選ぶ組み合わせの総数は二項係数 C(n, r) となるため、このアルゴリズムの時間計算量は O(C(n, r)) となります。r = n/2 のとき組み合わせ数が最大になるため、最悪の場合の計算量は指数関数的に増加することに留意してください。

まとめ

このように再帰的なバックトラッキングを使うことで、配列から指定サイズのすべての部分集合を効率よく列挙できます。「要素を選ぶ／選ばない」という 2 択の分岐を繰り返すシンプルな構造なので、部分和問題やナップサック問題など、他の組み合わせ問題への応用も容易です。