[골5] 9084 - 동전

#include <iostream>

using namespace std;

#pragma region 입출력 속도향상

#define FAST_IO() \
{\
	ios::sync_with_stdio(false);\
	cin.tie(NULL); \
	cout.tie(NULL); \
}\

#pragma endregion

int main()
{
	FAST_IO();

	int t;
	cin >> t;

	while (t--)
	{
		int n;
		cin >> n;
		int coin[21] = { 0 };

		for (int i = 1; i <= n; i++)
			cin >> coin[i];

		int m;
		cin >> m;

		// n가지 동전 1 ≤ M ≤ 10000
		int dp[10001] = { 0 };
		dp[0] = 1;

		for (int i = 1; i <= n; i++)
		{
			for (int j = coin[i]; j <= m; j++)
				dp[j] += dp[j - coin[i]];
		}
		cout << dp[m] << '\n';
	}
	return 0;
}