22真题
作者:
秋天的夜
,
2024-11-25 10:16:08
,
所有人可见
,
阅读 5
//这一道题其实就是回溯法搜索
//思路:物品不能重复利用,N个数是正的
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>path;
int nums[110];
int N;
int target;
int flag=0;
void dfs(int n,int postion){
if(n==0){
//说明找到了,于是输出
flag=1;
for(int i=0;i<path.size();i++){
cout<<path[i]<<" ";
}
cout<<endl;
}
//否则就是可以继续遍历
for(int i=postion;i<N;i++){
//这样可以保证不重复
if(n-nums[i]>=0){
//于是可以继续递归
path.push_back(nums[i]);
dfs(n-nums[i],i+1);
//然后恢复现场
path.pop_back();
}
else{
break;
}
}
}
int main(){
cin>>N>>target;
for(int i=0;i<N;i++){
cin>>nums[i];
}
sort(nums,nums+N);
if(nums[0]>target){
cout<<"none";
return 0;
}
//否则就是可以dfs
dfs(target,0);
if(flag==0)cout<<"none";
return 0;
}