题目描述

给定N个正整数A1,A2,…,AN，从中选出若干个数，使它们的和为M，求有多少种选择方案。

• 输入格式
  第一行包含两个整数N和M。
  第二行包含N个整数，表示A1,A2,…,AN
• 输出格式
  包含一个整数，表示可选方案数。
• 数据范围
  1≤N≤100,
  1≤M≤10000,
  1≤Ai≤1000
• 输入样例：
  4 4
  1 1 2 2
• 输出样例：
  3

算法分析

时间复杂度

$ O(nm) $

参考文献

算法提高课

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std ;

const int N = 100010 ;
int f[N] ;

int n,m ;

int main(){
    cin >> n >> m ;

    f[0] = 1 ;
    for(int i=1;i<=n;i++){
        int a ;
        cin >> a ;
        for(int j=m;j>=a;j--){
            f[j] = f[j] + f[j-a] ;
        }
    }

    cout << f[m] << endl ;

    return 0 ;
}