C++で指定された条件を満たす部分集合の個数を数える方法

数値の配列 arr[] と整数 x が入力として与えられたとき、次の条件を満たす部分集合（サブセット）をすべて見つけたいと思います。その条件とは、「部分集合に含まれる各要素が x で割り切れ、かつそれらの合計も x で割り切れる」というものです。

例

入力

arr[] = {1,2,3,4,5,6} x=3

出力

条件を満たす部分集合の個数：3

説明

該当する部分集合は以下の通りです：
[3], [6], [3,6]

入力

arr[] = {1,2,3,4,5,6} x=4

出力

条件を満たす部分集合の個数：1

説明

該当する部分集合は以下の通りです：
[4]

このプログラムで採用しているアプローチは以下の通りです −

このアプローチでは、まず配列 arr[] の中から x で完全に割り切れる要素の個数を数えます。その個数を count としたとき、2^count−1 を条件を満たす部分集合の総数として返します。これは、割り切れる各要素について「部分集合に含める／含めない」の2択があるため組み合わせは 2^count 通りとなり、そこから空集合の1つを除いた値が答えになるためです。

• 整数型の配列 arr[] を用意します。

• x を入力として受け取ります。

• 関数 sub_sets(int arr[], int size, int val) は、配列と x を受け取り、条件を満たす部分集合の個数を返します。

• x が 1 の場合、すべての要素を割り切るため、答えは 2ⁿ−1（n は配列のサイズ）となります。

コード例

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int sub_sets(int arr[], int size, int val){
   int count = 0;
   if (val == 1){
      count = pow(2, size) - 1;
      return count;
   }
   for (int i = 0; i < size; i++){
      if (arr[i] % val == 0){
         count++;
      }
   }
   count = pow(2, count) - 1;
   return count;
}
int main(){
   int arr[] = { 4, 6, 1, 3, 8, 10, 12 }, val = 4;
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of sub-sets that satisfy the given condition are: "<<sub_sets(arr, size, val);
   return 0;
}

出力

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

Count of sub-sets that satisfy the given condition are: 7