278. 数字组合

算法：

转化为01背包问题

• $状态表示：\color{red}{f[i][j]}表示在A_1\sim A_i 选出若干数和为j的集合$
• $状态计算：f[i][j]=f[i-1][j]+f[i-1][j-x]$

代码：

#include<iostream>
using namespace std;
const int N=10010;
int f[N];

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

时间复杂度：$o(mn)$