题目描述

给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。

输入描述:
输入为两行:
第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)
第二行为n个正整数A [i] (32位整数)，以空格隔开。
输出描述:
输出所求的方案数

#include<stdio.h>
long long  dp[1005];
int  ori[1005];
int main()
{
    int N, M;
    int i,j;
    scanf("%d%d",&N,&M);
     
    for ( i = 0; i < N; i ++)
    {
     
        scanf("%d",&ori[i]);
    }
    dp[0] = 1;
    for (i = 0; i < N; i ++)
    {
        for (j = M; j >= ori[i]; j --)
        {
            dp[j] += dp[j - ori[i]];
        }
    }
    printf("%lld\n",dp[M]);
    return 0;
}