สมมติว่าเรามีอาร์เรย์ของตัวเลข n เราต้องหาเซตย่อยที่ไม่ว่างเพื่อให้ผลรวมขององค์ประกอบของเซตย่อยหารด้วย n ลงตัว ดังนั้น เราต้องส่งออกเซตย่อยดังกล่าวด้วยขนาดและดัชนีขององค์ประกอบในอาร์เรย์ดั้งเดิมเมื่อมีอยู่
ดังนั้น หากอินพุตเป็น [3, 2, 7, 1, 9] เอาต์พุตจะเป็น [2], [1 2]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดหนึ่งแผนที่ my_map
- เพิ่ม :=0
- สำหรับการเริ่มต้น i :=0 เมื่อ i
- add :=(add + arr[i]) mod N
- ถ้าบวกเหมือนกับ 0 แล้ว −
- พิมพ์ i + 1
- สำหรับการเริ่มต้น j :=0 เมื่อ j <=i อัปเดต (เพิ่ม j โดย 1) ทำ −
- พิมพ์ j + 1
- คืนสินค้า
- ถ้าเพิ่มใน my_map แล้ว −
- พิมพ์ (i - my_map[เพิ่ม])
- สำหรับการเริ่มต้น j :=my_map[add] + 1 เมื่อ j <=i อัปเดต (เพิ่ม j โดย 1) ทำ −
- พิมพ์ j + 1
- คืนสินค้า
- มิฉะนั้น
- my_map[เพิ่ม] :=ฉัน
ตัวอย่าง (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
