从n个数中选k个数之和为sum

xiufanivan · 2023-03-13 11:25:04 · 个人记录

题目描述：

从n个数中选k个数之和为sum，共有ans种

样例输入：

5 3 9
1 2 3 4 5

样例输出：

2

代码：

#include <bits/stdc++.h>
using namespace std;

// 从n个数中选k个数之和为sum，共有ans种 
int n, k, sum, ans = 0; 
int a[40];

// i：第几个数，cnt：选了几个数，s：总和 
void dfs(int i, int cnt, int s) {
    if (i == n) {
        if (cnt == k && s == sum) {
            ans++;
        }
        return;
    }
    // 不选 
    dfs(i + 1, cnt, s);
    // 选 
    dfs(i + 1, cnt + 1, s + a[i]);  // 这里必须写cnt+1或者++cnt，不能写cnt++ 
}

int main() {
    cin >> n >> k >> sum;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dfs(0, 0, 0);
    cout << ans << endl;

    return 0;
}