C++で要素の合計がNで割り切れる空でない部分集合を見つける方法

問題の概要

n個の整数からなる配列が与えられたとき、要素の合計がnで割り切れるような空でない部分集合(サブセット)を1つ見つけることを考えます。そのような部分集合が存在する場合は、そのサイズと、元の配列における該当要素のインデックスを出力します。

例えば、入力が [3, 2, 7, 1, 9] の場合、出力は次のようになります。

[2]
[1 2]

これは「サイズ2の部分集合であり、元の配列の1番目と2番目の要素(3 + 2 = 5)を選ぶと、合計がN=5で割り切れる」ことを意味しています。

アルゴリズムの考え方

この問題は累積和の剰余に着目することで効率的に解けます。先頭から順に累積和を計算し、それをNで割った余りを記録していきます。同じ余りが2回現れた場合、その2つの位置の間にある要素の合計は必ずNで割り切れます。また、鳩の巣原理より、余りの種類は高々N通りなので、必ず解が存在することが保証されます。

具体的な手順は以下の通りです。

1. 剰余を記録するためのマップ(my_map)を用意する
2. 累積和 add を 0 で初期化する
3. i = 0 から N-1 まで繰り返す:
   • add を (add + arr[i]) mod N で更新する
   • add が 0 の場合:先頭から i 番目までの要素の合計がNで割り切れるため、サイズ(i + 1)とインデックス 0〜i を出力して終了する
   • add がマップに既に存在する場合:my_map[add] + 1 番目から i 番目までの要素の合計がNで割り切れるため、サイズ(i - my_map[add])と該当するインデックスを出力して終了する
   • それ以外の場合:my_map[add] = i として現在の位置を記録する

この手法により、計算量はO(N)、追加の探索なしに解を得ることができます。

C++での実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
void subset_find(int arr[], int N) {
   unordered_map<int, int> my_map;
   int add = 0;
   for (int i = 0; i < N; i++) {
      add = (add + arr[i]) % N;
      if (add == 0) {
         cout << i + 1 << endl;
         for (int j = 0; j <= i; j++)
            cout << j + 1 << " ";
         return;
      }
      if (my_map.find(add) != my_map.end()) {
         cout << (i - my_map[add]) << endl;
         for (int j = my_map[add] + 1; j <= i; j++)
            cout << j + 1 << " ";
         return;
      }
      else
         my_map[add] = i;
   }
}
int main() {
   int arr[] = {3, 2, 7, 1, 9};
   int N = sizeof(arr) / sizeof(arr[0]);
   subset_find(arr, N);
}

入力例

{3, 2, 7, 1, 9}

出力結果

2
1 2

このように、累積和の剰余とハッシュマップを組み合わせることで、N個の整数の配列から「合計がNで割り切れる部分集合」を線形時間O(N)で効率的に発見できます。