7-16 monetary system I

7-16 The monetary system Ⅰ

To give you one n A monetary system of denominations , Find the face value of the composition as m How many currencies are there .

Input format
first line , Contains two integers n and m.

Next n That's ok , Each line contains an integer , Represents the face value of a currency .

Output format
All in one line , Contains an integer , Number of solutions .

Data range
n≤15,m≤3000

sample input ：

3 10
1
2
5

sample output ：

10

Code ：

#include<stdio.h>
int n,m;
int a[20];
int sum=0;
int vis[20][100000];
int find(int x,int money)
{
    
    if(money==m)
    {
    
        sum++;
        return 0;
    }
    if(money>m)
        return 0;
    if(x>=n)
        return 0;
    if(vis[x][money]!=0)
        return vis[x][money];
    int len=(m-money)/a[x];
    for(int i=len;i>=0;i--)
        vis[x][money]=find(x+1,money+a[x]*i)+a[x]*i;
}
int main()
{
    
    while( scanf("%d%d",&n,&m)!=EOF)
    {
    
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    find(0,0);
    printf("%d\n",sum);
        sum=0;
    }
}

202206260906 Japan