摘要：
数字组合时间限制：1秒内存限制：256MB提交：30解决方案：24[提交][状态][讨论板]主题描述找出N个数字中的M个。首先读入正整数N和M，然后读入N个正数。从N个数字中找出一个数字，使其总和为M。找出满足条件的所有数字组合，以计算组合数并输出组合数。您的程序需要运行不超过1秒。第一行输入是两个数字，分别代表N和M。第二行以N个数字开头。输出一个数字，表示M和的组合数。
数字组合
时间限制: 1 Sec 内存限制: 256 MB
提交: 30 解决: 24
[提交][状态][讨论版]
题目描述
在 N个数中找出其和为M的若干个数。先读入正整数N（1<N<100）和M(1<M<10000)， 再读入N个正数（可以有相同的数字，每个数字均在1000以内）， 在这N个数中找出若干个数， 使它们的和是M， 把满足条件的数字组合都找出来以统计组合的个数，输出组合的个数（不考虑组合是否相同）。要求你的程序运行时间不超过1秒。
输入
第一行是两个数字，表示N和M。
第二行起是N个数。
第二行起是N个数。
输出
一个数字，表示和为M的组合的个数。
样例输入
4 4
1 1 2 2
样例输出
3
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <map> #include <queue> #include <stack> #include <vector> #include <list> #include<functional> #define mod 1000000007 #define inf 0x3f3f3f3f #define pi acos(-1.0) using namespace std; typedef long long ll; const int N=105; const int M=10005; ll power(ll a,int b,ll c) {ll ans=1;while(b) {if(b%2==1) {ans=(ans*a)%c;b--;}b/=2;a=a*a%c;}return ans;} int a[N],n,m,dp[M]; int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) scanf("%d",&a[i]); dp[0]=1; for(int i=1; i<=n; i++) for(int j=m; j>=a[i]; j--) dp[j]+=dp[j-a[i]]; printf("%d",dp[m]); return 0; }