1 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long ll; // [1] 全局变量:n为输入的整数总个数,c为需要凑出的目标子集和 ll n,c; // [2] 全局数组:存储输入的n个整数(下标从1开始,符合输入顺序) ll arr[8000]; // [3] 全局向量:记录DFS过程中当前选中的数(即当前子集路径) vector<ll> dp; // [4] 全局标记:1表示未找到和为c的子集,0表示已找到(找到后终止所有递归) int flag=1; // [10] 自定义DFS函数:按输入顺序遍历数,尝试选/不选当前数,寻找和为c的子集 // 参数x:当前遍历到的数的索引(从1开始);参数sum:当前已选数的累加和 void dfs(ll x,ll sum){ // [11] 递归终止条件:已找到解/遍历完所有数/当前和超过目标和,直接返回 if(flag==0 || x >n || sum>c) return; // [12] 计算“选择当前数arr[x]”后的累加和 ll ans=sum+arr[x]; // [13] 选择当前数:将其加入当前路径(子集) dp.push_back(arr[x]); // [14] 找到目标解:选择当前数后累加和等于c if(ans == c){ // [15] 输出当前路径中的所有数(即满足条件的子集) for(int i=0;i<dp.size();i++){ cout<<dp[i]<<" "; } // [16] 标记为已找到解,后续递归会直接终止 flag=0; // [17] 终止当前递归分支 return; } // [18] 递归遍历下一个数:选择当前数的情况下,继续寻找 dfs(x+1,ans); // [19] 回溯操作:不选择当前数,从路径中移除 dp.pop_back(); // [20] 递归遍历下一个数:不选择当前数的情况下,继续寻找 dfs(x+1,sum); } // [5] 主函数:程序入口,处理输入、提前判断、启动DFS、输出结果 int main(){ // [6] 输入:读取整数个数n和目标子集和c cin>>n>>c; // [7] 定义变量ans:存储所有输入数的总和,用于提前判断无解情况 ll ans=0; // [8] 循环读取n个整数,存入数组并累加总和 for(int i=1;i<=n;i++) { cin>>arr[i]; // 读取第i个整数,存入arr[i] ans+=arr[i]; // 累加计算所有数的总和 } // [9] 提前判断:若所有数的总和小于目标和c,必然无解,直接输出提示并退出 if(ans<c){ cout<<"No Solution!"; return 0; } // [21] 启动DFS:从第1个数开始遍历,初始累加和为0 dfs(1,0); // [22] DFS结束后仍未找到解,输出无解提示 if(flag==1) { cout<<"No Solution!"; } // [23] 主函数正常退出 return 0; }
- 1
信息
- ID
- 1278
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者