3343785_tle.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, len[21];
int used[21], tot;
bool can;

bool cmp(int a,int b)
{
	return a > b;
}

void dfs(int need,int done)
{
	int i;

	if (done==0)
	{
		can = true;
		return ;
	}
	for (i = 0; !can && i < n; i++)
	{
		if (used[i]||len[i] > need)
		{
			continue;
		}
		if (len[i]==need)
		{
			used[i] = true;
			dfs(tot,done-1);
			used[i] = false;
			return ;
		}
		else
		{
			used[i] = true;
			dfs(need-len[i],done);
			used[i] = false;
		}
	}
}

int main()
{
	int i, cas;

	scanf("%d",&cas);
	while (cas--)
	{
		scanf("%d",&n);
		tot = 0;
		for (i = 0; i < n; i++)
		{
			scanf("%d",&len[i]);
			tot += len[i];
		}
		if (tot%4!=0)
		{
			puts("no");
			continue;
		}
		tot /= 4;
		memset(used,0,sizeof(used));
		sort(len,len+n,cmp);
		can = false;
		dfs(tot,4);
		puts(can?"yes":"no");
	}
	return 0;
}