サブセットの要素の合計がC++でNで割り切れるような、N個の整数の配列で空でないサブセットを見つけます

n個の数の配列があるとします。サブセットの要素の合計がnで割り切れるような、空でないサブセットを見つける必要があります。そのため、そのようなサブセットを、元の配列に存在する場合は、そのサイズと要素のインデックスとともに出力する必要があります。

したがって、入力が[3、2、7、1、9]の場合、出力は[2]、[12]になります。

これを解決するには、次の手順に従います-

• 1つのマップmy_mapを定義する
• 追加：=0
• iを初期化する場合：=0、i
• add：=（add + arr [i]）mod N
• addが0と同じ場合、-
  • print i + 1
  • jを初期化する場合：=0、j <=iの場合、更新（jを1つ増やす）、実行-
    • print j + 1
  • 戻る
• my_mapに追加する場合は、-
  • print（i --my_map [add]）
  • jを初期化する場合：=my_map [add] + 1、j <=iの場合、更新（jを1つ増やす）、実行-
    • print j + 1
  • 戻る
• それ以外の場合
  • my_map [add]：=i

例（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