นับ Subset ที่ทุกองค์ประกอบและผลรวมหาร x ลงตัว ใน C++

โจทย์: ให้อาร์เรย์ arr[] และจำนวน x ต้องการนับ Subset ที่:

1. ทุกองค์ประกอบใน subset หาร x ลงตัว
2. ผลรวมของ subset หาร x ลงตัว

ข้อสังเกตสำคัญ

เงื่อนไขที่ 1 หมายถึง subset ต้องประกอบด้วยองค์ประกอบที่หาร x ลงตัวเท่านั้น
เงื่อนไขที่ 2 จะเป็นจริงอัตโนมัติ เพราะผลรวมของตัวเลขที่หาร x ลงตัว ก็จะหาร x ลงตัว

ดังนั้น โจทย์ลดรูปเหลือ: นับ Subset ที่ไม่ว่างเปล่า ที่ประกอบด้วยองค์ประกอบที่หาร x ลงตัว

สูตร

ให้ count = จำนวนองค์ประกอบใน arr[] ที่หาร x ลงตัว
จำนวน subset = 2^count - 1 (ลบ subset ว่าง)

โค้ด C++

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

int sub_sets(int arr[], int size, int val) {
    int count = 0;
    if (val == 1) {
        count = pow(2, size) - 1;
        return count;
    }
    for (int i = 0; i < size; i++) {
        if (arr[i] % val == 0) count++;
    }
    count = pow(2, count) - 1;
    return count;
}

int main() {
    int arr[] = {4, 6, 1, 3, 8, 10, 12};
    int val = 4;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << sub_sets(arr, size, val);
    return 0;
}

ผลลัพธ์

Count of sub-sets that satisfy the given condition are: 7

คำอธิบายตัวอย่าง

arr = {4, 6, 1, 3, 8, 10, 12}, x = 4
องค์ประกอบที่หาร 4 ลงตัว: 4, 8, 12 → 3 ตัว
Subset = 2³ - 1 = 7 subsets:
{4}, {8}, {12}, {4,8}, {4,12}, {8,12}, {4,8,12}