นับ Subset ที่มีเลขคู่ที่ต่างกันทั้งหมดใน C++

เราได้รับอาร์เรย์จำนวนเต็มบวก เป้าหมายคือหา subset ที่มีเลขคู่ที่ distinct (ไม่ซ้ำ) ทั้งหมด Subset ที่มีสมาชิกเหมือนกันนับเป็น 1

ตัวอย่าง

อินพุต: arr[] = {1, 3, 5, 7, 8, 3, 2}

เอาต์พุต: 3

คำอธิบาย: [2], [8], [2,8]

อินพุต: arr[] = {2, 4, 6}

เอาต์พุต: 7

คำอธิบาย: [2], [4], [6], [2,4], [2,6], [4,6], [2,4,6]

แนวทางการแก้ปัญหา

นับจำนวน distinct even numbers ในอาร์เรย์ (ใช้ unordered_set) สมมติมี c ตัว จำนวน subset = 2c - 1 (ลบ empty set)

การนำไปใช้ (Implementation)

#include <bits/stdc++.h>
using namespace std;

int subset_even(int arr[], int size) {
    unordered_set<int> un_set;
    for (int i = 0; i < size; i++) {
        if (arr[i] % 2 == 0) {
            un_set.insert(arr[i]);
        }
    }
    int count = un_set.size();
    return pow(2, count) - 1;
}

int main() {
    int arr[] = {10, 4, 21, 3, 5, 7, 6, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of subsets having distinct even numbers are: " << subset_even(arr, size);
    return 0;
}

เอาต์พุต

Count of subsets having distinct even numbers are: 15