算法2

动态规划

O(n*m）

参考文献

acwing算法提高课

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
int f[maxn];

int main()
{
    int n;
    int m;
    cin>>n>>m;
    f[0]=1;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        for(int j=m;j>=x;j--)
        {
            f[j]=f[j]+f[j-x];
        }
    }
    cout<<f[m]<<endl;

}