zju1204_dfs.cpp

这是浙大acm,北大acm上,还有地大acm上的题解,全部是关于搜索算法的,题目文件名上有

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int temp[33], inx, n;
int num[50];
bool ok, have[1005];

void search(int k, int len, int sum)
{
	if(inx > len) return;
	if(sum <= 1000 && inx == len && have[sum]) {
		ok = true;
		for(int i = 0; i < inx-1; i++) {
			cout<<temp[i]<<"+";
		}
		cout<<temp[inx-1]<<"="<<sum<<endl;
		return ;
	}
	for(int i = k; i < n; i++) {
		if(inx + 1 > len) return ;
		if(sum + num[i] > num[n-1]) return ;///*
		if(inx+1 <= len) {
			temp[inx++] = num[i];
			search(i+1, len, sum+num[i]);
			inx--;
		}
	}
	return ;
}

int main()
{
	int tcase;
	scanf("%d", &tcase);
	while(tcase--) {
		scanf("%d", &n);
		memset(have, false, sizeof(have));
		for(int i = 0; i < n; i++) {
			scanf("%d", &num[i]);
			have[num[i]] = true;
		}
		sort(num, num+n);		
		ok = false;
		for(int len = 2; len < n; len++) {
			inx = 0;
			search(0, len, 0);
		}
		if(!ok) cout<<"Can't find any equations."<<endl;
		cout<<endl;
	}
	return 0;
}
/*
5
3 1 2 3
3 1 2 5
6 1 2 3 5 4 6

*/