- 쉬운 정렬 문제였다.
- 문제 접근 방법을 생각하는데 오래 결렸다.
- Meet int the middle을 통해 시간을 줄일 수 있음.
- 완전 탐색을 통해 문제를 해결하려 할때 TLE 가 난다면 한번쯤 생각해 볼만한 풀이 인거 같다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, want, arr[50];long long ans;
vector<int> v1[2],v2[2];
int main() {
scanf("%d %d", &n, &want);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
if (n == 1) {
if (arr[0] == want) printf("1");
else printf("0");
return 0;
}
v1[0].push_back(arr[0]);
v1[0].push_back(0);
v2[((n-1) % 2)].push_back(0);
v2[((n-1)%2)].push_back(arr[n - 1]);
int max_idx = n % 2 == 0 ? n / 2-1 : n / 2;
int v1idx=0, v2idx;
v2idx = (n - 1) % 2;
for (int i = 1; i <= max_idx; i++) {
v1idx = i%2;
for (int j = 0; j < v1[!v1idx].size(); j++) {
v1[v1idx].push_back(v1[!v1idx][j]);
v1[v1idx].push_back(v1[!v1idx][j] + arr[i]);
}
v1[!v1idx].clear();
if (!((n % 2 == 1) && i == max_idx)) {
v2idx = (n-i-1)%2;
for (int j = 0; j < v2[!v2idx].size(); j++) {
v2[v2idx].push_back(v2[!v2idx][j] + arr[n - i - 1]);
v2[v2idx].push_back(v2[!v2idx][j]);
}
v2[!v2idx].clear();
}
}
sort(v1[v1idx].begin(), v1[v1idx].end());
for (int i = 0; i < v2[v2idx].size(); i++) {
int idx = lower_bound(v1[v1idx].begin(), v1[v1idx].end(), want-v2[v2idx][i])-v1[v1idx].begin();
int idx2 = upper_bound(v1[v1idx].begin(), v1[v1idx].end(), want - v2[v2idx][i]) - v1[v1idx].begin();
ans += (long long)(idx2 - idx);
}
if (!want) ans--;
printf("%lld", ans);
}
