## Dynamic Programming: Number Combination

Given N Positive integer A1,A2, … ,AN, Select a subset of numbers from them so that their sum is M, How many options are there?

Input format The first line contains two integers N with M.

The second line contains N Integers, representing A1,A2, … ,AN.

Output format Contains an integer, indicating the number of options.

data range 1 ≤ N≤ 100, 1 ≤ M≤ 10000, 1 ≤Ai≤ 1000

Sample Input:

```
4 4
1 1 2 2
```

Sample Output:

```
3
```

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std ;
const int N = 100010 ;
// number of ways to get N
int dp[N] ;
int n,m ;
int main(){
cin >> n >> m ;
// nothing is chosen, there's 1 way
dp[0] = 1 ;
for(int i=1;i<=n;i++){
int a ;
cin >> a ;
/* solution using 2D dp
for(int j=m;j>=0;j--){
if (j>a)
dp[i][j] = dp[i-1][j] + dp[i-1][j-a] ;
else
dp[i][j] = dp[i-1][j];
}
*/
for(int j=m;j>=a;j--){
dp[j] = dp[j] + dp[j-a] ;
}
}
cout << f[m] << endl ;
return 0 ;
}