หาสับเซ็ตที่ไม่ว่างซึ่งผลรวมหารด้วย N ลงตัวใน C++

โจทย์

ให้อาร์เรย์ของจำนวน n ตัว ต้องการหาสับเซ็ตที่ไม่ว่างซึ่งผลรวมของสมาชิกในสับเซ็ตหารด้วย n ลงตัว ต้องแสดงสับเซ็ตใดสับเซ็ตหนึ่งพร้อมขนาดและดัชนีของสมาชิกในอาร์เรย์ต้นฉบับ

ตัวอย่าง: อินพุต [3, 2, 7, 1, 9] → เอาต์พุต [2], [1 2]

ขั้นตอนการแก้ปัญหา

• สร้าง map my_map
• กำหนด add := 0
• วนลูป i := 0 ถึง N-1:
  • add := (add + arr[i]) mod N
  • ถ้า add == 0 แสดง i+1 และดัชนี 1 ถึง i+1 แล้ว return
  • ถ้า add อยู่ใน my_map แล้ว แสดง (i - my_map[add]) และดัชนี my_map[add]+1 ถึง i+1 แล้ว return
  • มิฉะนั้น 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