範例程式碼 uva12911
//uva12911
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int N, T;
while (cin >> N >> T) {
long long int num[45];
for (int i = 0; i < N; ++i)
cin >> num[i];
// divide into two subset because enumerate the 2^40 subset is impossible
long long int lNum = N / 2;
if (lNum == 0)
lNum = 1;
long long int rNum = N - lNum;
unordered_map<long long int, int> mL, mR; // sum maps to number of subsets
// enumerate 1~2^(left)
for (int i = 1; i < (1 << lNum); ++i) {
long long int sum = 0;
for (int j = 0; j < lNum; ++j) {
if (i & (1 << j))
sum += num[j];
}
++mL[sum];
}
// enumerate 1~2^(right)
for (int i = 1; i < (1 << rNum); ++i) {
long long int sum = 0;
for (int j = 0; j < rNum; ++j) {
if (i & (1 << j))
sum += num[lNum + j];
}
++mR[sum];
}
long long int cnt = 0;
for (auto itr : mL) {
if (mR.find(T - itr.first) != mR.end())
cnt += (long long)itr.second * mR[T - itr.first];
}
cout << cnt + mL[T] + mR[T] << endl;
}
return 0;
}