BOJ-5557

#include<iostream>
#include<cstring>

using namespace std;

#define MAX 101

int N;
int arr[MAX];
long long DP[MAX][1001];
int result;

long long checkDP(int index, int sum) {
	if (sum < 0 || sum > 20) return 0;
	if (index == N - 2) {
		if (sum == result)
			DP[index][sum] = 1;
		else
			DP[index][sum] = 0;
		return DP[index][sum];
	}

	if (DP[index][sum] != -1)
		return DP[index][sum];

	long long check = 0;

	check += checkDP(index + 1, sum + arr[index + 1]);
	check += checkDP(index + 1, sum - arr[index + 1]);

	return DP[index][sum] = check;
}

int main() {
    ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;

	for (int i = 0; i < N - 1; i++)
		cin >> arr[i];

	cin >> result;
    // memset function => set memory's value with wanted size!
	memset(DP, -1, sizeof(DP));
    
	cout << checkDP(0, arr[0]);
	return 0;
}