Tìm một tập con không rỗng trong một mảng N số nguyên sao cho tổng các phần tử của tập con chia hết cho N trong C ++

Giả sử chúng ta có một mảng gồm n số; chúng ta phải tìm một tập con khác rỗng sao cho tổng các phần tử của tập con chia hết cho n. Vì vậy, chúng ta phải xuất ra bất kỳ tập hợp con nào như vậy với kích thước của nó và chỉ số của các phần tử trong mảng ban đầu khi nó có mặt.

Vì vậy, nếu đầu vào là [3, 2, 7, 1, 9], thì đầu ra sẽ là [2], [1 2].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ my_map
• thêm:=0
• để khởi tạo i:=0, khi i
• thêm:=(add + arr [i]) mod N
• nếu thêm giống 0, thì -
  • in i + 1
  • để khởi tạo j:=0, khi j <=i, cập nhật (tăng j lên 1), thực hiện -
    • in j + 1
  • trở lại
• nếu thêm vào my_map, thì -
  • print (i - my_map [add])
  • để khởi tạo j:=my_map [add] + 1, khi j <=i, cập nhật (tăng j lên 1), thực hiện -
    • in j + 1
  • trở lại
• Mặt khác
  • my_map [thêm]:=i

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

{3, 2, 7, 1, 9}

Đầu ra

2
1 2