Tìm tập con không rỗng có tổng chia hết cho N trong mảng N số nguyên (C++)

Cho mảng n số nguyên, cần tìm một tập con không rỗng sao cho tổng các phần tử của tập con đó chia hết cho n. Chương trình sẽ xuất kích thước tập con và các chỉ số của các phần tử trong mảng gốc.

Ví dụ: với mảng [3, 2, 7, 1, 9], kết quả là [2], [1 2] (tập con có 2 phần tử tại vị trí 1 và 2).

Các bước giải:

• Khởi tạo một map my_map để lưu trữ phần dư.
• Biến add := 0 lưu tổng prefix modulo N.
• Duyệt mảng từ i = 0 đến N-1:
  • Cập nhật add := (add + arr[i]) % N.
  • Nếu add == 0: in ra i+1 và các chỉ số từ 1 đến i+1, sau đó kết thúc.
  • Nếu add đã tồn tại trong my_map: in ra độ dài đoạn (i - my_map[add]) và các chỉ số từ my_map[add]+2 đến i+1, sau đó kết thúc.
  • Ngược lại, lưu my_map[add] := i.

Ví dụ (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);
}

Đầu vào

{3, 2, 7, 1, 9}

Đầu ra

2 1 2