9084 동전

#include <stdio.h>
#include <string.h>
 
using namespace std;
 
int coin[25] = { 0 };
int dp[25][10005] = { 0 };
 
int main() {
    int t;
    scanf("%d", &t);
 
    while (t--) {
        int num;
        scanf("%d", &num);
 
        for (int i = 1; i <= num; i++) {
            scanf("%d", &coin[i]);
        }
 
        int money;
        scanf("%d", &money);
 
        for (int i = 1; i <= num; i++) {
            dp[i][0] = 1;
        }
 
        for (int j = 1; j * coin[1] <= money; j++) {
            dp[1][coin[1] * j] = 1;
        }
 
        for (int i = 2; i <= num; i++) {
            for (int j = 1; j <= money; j++) {
                int sum = 0;
                for (int k = 0; k*coin[i] <= j; k++) {
                    sum += dp[i - 1][j - k * coin[i]];
                }
 
                dp[i][j] = sum;
            }
        }
 
        printf("%d\n", dp[num][money]);
        /*
        for (int i = 1; i <= num; i++) {
            for (int j = 1; j <= money; j++) {
                printf("%d ", dp[i][j]);
            }
            printf("\n");
        }
        */
        for (int i = 1; i <= num; i++) {
            memset(dp[i], 0, sizeof(int) * 10004);
        }
        memset(coin, 0, sizeof(int) * 24);
    }
}