DFS模板 题目地址 L3-001 凑零钱 (30 分)

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

int N[MAX],vis[MAX],result[MAX], flag, tmp;
int t, n,m;;
void DFS(int Index,int sum) {
	if(sum > m)
		return;
	if(sum == m) {
		flag = 1;
		for(int i = 0; i < tmp; i++) 
			i == tmp - 1 ? printf("%d\n",result[i]) : printf("%d ",result[i]);		
		return;
	}
	for(int i = Index; i < n; i++) {
		if(!vis[i] && !flag) {
			vis[i] = 1;
			result[tmp++] = N[i];
			DFS(i + 1,sum + N[i]);
			result[--tmp] = 0;
			vis[i] = 0;
		}
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 0;i < n; i++)  {
		scanf("%d",&N[i]);
		t += N[i];
	}
	sort(N,N+n);
	if(N[0] > m || t < m)
		printf("No Solution\n");
	else{
		DFS(0,0); 
		flag == 0 ? printf("No Solution\n") : 0;
	} 
	return 0;
}