Lời giải: Đếm số tập con có tổng đúng bằng \(S\)

Tư duy

Với \(N \le 20\) ta có \(2^N\) tập con, hoàn toàn khả thi để duyệt hết. Ý tưởng là với mỗi mask, tính tổng của tập con tương ứng và đếm những mask nào có tổng đúng bằng \(S\).

Thuật giải

Với mỗi mask, ta tính dp[mask] bằng kỹ thuật "tách bit thấp nhất":

• Lấy lsb = mask & -mask – bit thấp nhất của mask.
• Phần còn lại là mask ^ lsb.
• Tổng dp[mask] = dp[mask ^ lsb] + a[vị_trí_của_lsb].

Nếu dp[mask] == S ta tăng biến đếm.

Đánh giá độ phức tạp

• Thời gian: \(O(N \cdot 2^N)\) – chạy nhanh với \(N \le 20\).
• Bộ nhớ: \(O(2^N)\).

Mã nguồn tham khảo

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, S;
    if (!(cin >> n >> S)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int full = 1 << n;
    vector<int> dp(full, 0);
    int cnt = 0;
    for (int mask = 0; mask < full; mask++) {
        if (mask == 0) { dp[0] = 0; continue; }
        int lsb = mask & -mask;
        int bit = __builtin_ctz(lsb);
        dp[mask] = dp[mask ^ lsb] + a[bit];
        if (dp[mask] == S) cnt++;
    }

    cout << cnt << "\n";
    return 0;
}