Đếm tập con có các số chẵn phân biệt trong C++

Cho mảng số nguyên dương. Tìm các tập con (subset) chỉ chứa các số chẵn phân biệt. Tập con cùng phần tử nhưng khác thứ tự chỉ đếm 1 lần. Ví dụ [2,4,6] và [6,2,4] là cùng một tập.

Ví dụ

Đầu vào: arr[] = {1,3,5,7,8,3,2}
Đầu ra: 3 ([2], [8], [2,8]).

Đầu vào: arr[] = {2,4,6}
Đầu ra: 7 (tất cả tập con không rỗng của {2,4,6}).

Giải thuật

Đếm số lượng số chẵn phân biệt trong mảng (dùng unordered_set). Nếu có c số chẵn phân biệt → số tập con không rỗng = 2^c - 1.

Ví dụ triển khai

#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();
    count = pow(2, count) - 1;
    return count;
}

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

Kết quả

Count of subsets having distinct even numbers are: 15