L3-001 凑零钱

一道很简单的DFS。

#include <bits/stdc++.h>
using namespace std;
int n,m,a[10010];
vector<int> res;
void dfs(int start,int own){
	for(int i=start;i<n;i++){
		if(own+a[i]>m) return;
		else if(own+a[i]==m){
			res.push_back(a[i]);
			int flag =0;
			for(int i=0;i<res.size();i++){
				if(flag) cout << " ";
				cout << res[i];
				flag++;
			}
			exit(0);
		}else{
			res.push_back(a[i]);
			dfs(i+1,own+a[i]);
			res.pop_back();
		}
	}
}
int main(){
	cin>>n>>m;
	int sum = 0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		sum += a[i];
	}
	if(sum<m){
		cout << "No Solution" << '\n';
		return 0;
	}
	sort(a,a+n);
	dfs(0,0);
	cout << "No Solution"<<'\n';
	return 0;
}