2553 得到整数X
大约 2 分钟
2553 得到整数X
【算法】 子集枚举、DFS / 位运算
【C++】 递归、位运算、子集枚举
【难度】 入门
一、题目简述
小黑有 个互不相同的正整数(),每个数不超过 100。从中选若干个数(无重复),通过加法凑出 ()。求不同的方案数。
二、解题思路
由于 ,每个数可选可不选,共有 种方案。可以直接枚举所有子集。
方法:DFS / 递归
递归函数 dfs(idx, sum):
- 如果
sum == X,方案数 +1 - 如果
idx == n或sum > X,回溯 - 两种选择:选
a[idx]或不选
注意方案数计算时机:应该在 sum == X 时计数但继续递归(因为可能有 0 值?题目说正整数,所以不会)。计数后返回或继续取决于是否还有更多。
更简洁的做法: 在递归中,选和不选分别递归,到达末尾时检查 sum。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int n, X;
int a[25];
int ans = 0;
void dfs(int idx, int sum) {
if (sum == X) {
ans++;
// 注意:不能直接 return,因为后面的数可能是 0
// 但题目说正整数,所以后面的数加进来只会更大,可以 return
return;
}
if (idx == n || sum > X) {
return;
}
// 不选 a[idx]
dfs(idx + 1, sum);
// 选 a[idx]
dfs(idx + 1, sum + a[idx]);
}
int main() {
cin >> n >> X;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
dfs(0, 0);
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间:, 时约 次递归调用,在 1 秒内可以完成。
- 空间:,递归栈深度最多 。
五、知识扩展
位运算枚举子集
int ans = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
sum += a[i];
}
}
if (sum == X) ans++;
}两种写法复杂度相同,。DFS 版加了 sum > X 剪枝后实际更快。
