【C++】配列内の異なる偶数から作れる部分集合の数を数える方法

問題の概要

正の整数からなる配列が与えられたとき、その中から異なる偶数のみを含む部分集合(サブセット)がいくつ作れるかを求めます。要素がまったく同じ集合は重複してカウントせず、1つとして数えます。たとえば [2, 4, 6] と [6, 2, 4] は順序が違うだけなので、同じ集合として扱います。

具体的な例で確認してみましょう。

例1

入力: arr[] = {1, 3, 5, 7, 8, 3, 2}

出力: 異なる偶数を含む部分集合の数 → 3

解説: 配列に含まれる偶数は 8 と 2 の2種類です。作られる部分集合は [2]、[8]、[2, 8] の3つになります。

例2

入力: arr[] = {2, 4, 6}

出力: 異なる偶数を含む部分集合の数 → 7

解説: 偶数が3種類あるため、[2]、[4]、[6]、[2,4]、[2,6]、[4,6]、[2,4,6] の7つの部分集合が作れます。

アルゴリズムの考え方

この問題は、次の数学的な性質を使うと非常にシンプルに解けます。

まず、配列内に現れる重複しない偶数をすべて集めます。その個数を n とすると、n 個の要素から空でない部分集合を作る組み合わせの総数は次の式で表せます。

部分集合の総数 = 2ⁿ − 1

(「−1」は空集合を除外するためです)

処理の手順

• 整数型の配列 arr[] を受け取る関数 subset_even(int arr[], int size) を定義します。
• 初期カウントを 0 に設定します。
• 重複排除のために unordered_set<int> を用意します。
• for ループで配列を走査し、arr[i] % 2 == 0 となる要素(偶数)を set に挿入します。
• set のサイズ(un_set.size())が「異なる偶数の個数」になります。
• count = pow(2, count) - 1 を計算して結果を返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

int subset_even(int arr[], int size){
    int count = 0;
    unordered_set<int> un_set;
    // 配列を走査して偶数のみをsetに格納(自動的に重複が除去される)
    for(int i=0; i<size; i++){
        if (arr[i] % 2 == 0){
            un_set.insert(arr[i]);
        }
    }
    unordered_set<int>::iterator i;
    count = un_set.size(); // 異なる偶数の個数
    count = pow(2, count) - 1; // 空集合を除いた部分集合の総数
    return count;
}

int main(){
    int arr[] = {10, 4, 21, 3, 5, 7, 6, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of subsets having distinct even numbers are: "<<subset_even(arr, size);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of subsets having distinct even numbers are: 15

この例では、配列 {10, 4, 21, 3, 5, 7, 6, 8} のうち偶数は 10、4、6、8 の4種類です。したがって 2⁴ − 1 = 15 個の部分集合が存在することになり、計算結果と一致します。

まとめ

本記事では、配列内の重複しない偶数から作れる部分集合の数を求める方法を紹介しました。ポイントは以下の2つです。

• unordered_set を使うことで、偶数の抽出と重複除去を同時に実現できる。
• n 個の異なる要素から空でない部分集合を作る場合、その総数は 2ⁿ − 1 という公式で一発計算できる。

このアプローチにより、ループで全部分集合を列挙する必要がなくなり、時間計算量 O(n) という効率的な実装が可能になります。