# 【CF】A. Fivesteps

## [題目連結](https://codeforces.com/group/AXj32pLpIx/contest/468825/problem/A)

## **時間複雜度**

* $O(2^\frac{N}{2})$

## **解題想法**

這一題從測資基本上就可以看出是要用折半枚舉去處理了，處理的方法是先枚舉陣列中前半每個位置的正跟負，並將結果記錄下來，最後枚舉後半所有位置的正負並計算答案就可以了

值得注意的是，枚舉前半的結果可以利用 `map` 來儲存，用以計算某個結果有幾種可能性

## **完整程式**

/* Question : CF 【2023 MD Player Training】 Simulation Contest 1 - A. Fivesteps */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 40 + 50;
const int Mod = 1e9 + 7;
int n, x, res, arr[MAXN];
map<int, int> mp;

void f1( int cnt, int amt, int sum ){
    if( cnt == amt + 1 ){
        mp[sum]++;
        return;
    }

    f1(cnt+1, amt, sum + arr[cnt]);
    f1(cnt+1, amt, sum - arr[cnt]);
}

void f2( int cnt, int amt, int sum, int tar ){
    if( cnt == amt + 1 ){
        res += mp[tar-sum];
        return;
    }

    f2(cnt+1, amt, sum+arr[cnt], tar);
    f2(cnt+1, amt, sum-arr[cnt], tar);
}

signed main(){
    opt;
    cin >> n >> x;
    for( int i = 1 ; i <= n ; i++ ) cin >> arr[i];

    f1(1, n/2, 0);
    f2(n/2+1, n, 0, x);

    cout << res << "\n";
}