题解 | #数字和为sum的方法数#

#include <iostream>
using namespace std;
const int MAXN = 1e3+5;
#define ll long long
int a[MAXN],n,sum;
ll dp[MAXN][MAXN];
//dp[i][j]: 前i个数组成j的方案数
int main() {
    cin>>n>>sum;
    for(int i=0;i<n;i++) cin>>a[i];
    dp[0][a[0]] = 1;
    for(int i=1;i<n;i++){
        for(int j=0;j<=sum;j++){
            //
            dp[i][j] = dp[i-1][j];
            if(j>=a[i]) dp[i][j] += dp[i-1][j-a[i]];//选择第i个数
            if(j==a[i]) dp[i][j] += 1;//第i个数可单独组成j
        }
    }
    cout<<dp[n-1][sum]<<endl;
}
// 64 位输出请用 printf("%lld")