题目描述

blablabla

样例

blablabla

算法1

(递归)

C++ 代码

#include <iostream>
using namespace std;

const int N = 1010;

int n, m;
int a[N];  // 用于存储输入的n个不同正整数
int cnt;

// DFS函数，cur表示当前考虑的数字下标，sum表示当前已选数字的和
void Dfs(int cur, int sum) {
    if (sum == m) {
        cnt++;
        return;
    }

    if (cur == n || sum > m) return;  // 如果已经遍历完所有数字或者当前和超过了m，就回溯

    // 不选当前数字，继续考虑下一个数字
    Dfs(cur + 1, sum);
    // 选择当前数字，然后继续考虑下一个数字
    Dfs(cur + 1, sum + a[cur]);

}

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

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    Dfs(0, 0);
    cout << cnt << endl;
    return 0;
}