題意#
你手上有 \( n \) 枚硬幣，每枚硬幣都有各自的面額。
你的任務是找出：利用這幾枚硬幣，你總共可以湊出幾種不同的金額？並把所有能湊出來的金額由小到大列印出來。
思路#
這題的核心概念是 0/1 背包問題的變形，但在這我們只需要關心「這個金額能不能湊出來」，也就是一個布林值（True 或是 False）。
既然只需要儲存 0 狀態 跟 1 狀態，我們最直覺的作法是開一個布林的 dp 陣列，然後對於每一枚新的硬幣（面額 x），去檢查之前所有能湊出來的金額 v，把它變成能湊出 v + x 的狀態。
但既然狀態只有 0 跟 1，C++ 裡面有一個為這量身打造的超強武器：bitset！
我們可以把整個可達成的金額狀態看成一長串的 bit（如果第 i 個 bit 是 1，代表金額 i 湊得出來）。
當我們拿到一枚面額為 x 的硬幣時，其實就是把原本所有能湊出來的金額統統加上 x。在位元運算裡面，這就等於是把整個 bitset 往左平移 x 格（bs << x）。
然後我們再把平移後的新狀態，跟原本舊狀態做個位元聯集（|），意思是「維持原本湊得出來的金額」加上「新湊出來的這些金額」。
這個 bs |= bs << x 的寫法，不僅程式碼極度精簡，底層位元運算更能一次處理多個狀態，比起用迴圈跑 DP，效能快上非常多。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
// 總面額上限是 100 * 1000 = 100000，所以開到 100001
bitset<100001> bs;
// bs.set(0, 1) 代表湊出 0 元的方法永遠可行
bs.set(0, 1);
int n;
for (cin >> n; n--;) {
int x; cin >> x;
// 把舊的狀態左移 x 位，相當於所有能湊出的金額加上 x
// 然後和舊狀態做 OR 運算，合併成新的可用狀態
bs |= bs << x;
}
// count() 會計算裡面有幾個 1
// 因為 0 元不算在題目要的答案裡，所以要扣掉 1
cout << bs.count() - 1 << '\n';
// 依序印出所有可以湊出來的金額
for (int i = 1; i <= 100000; i++) {
if (bs[i]) cout << i << ' ';
}
}
