C语言解答

#include<stdio.h>
#include<stdlib.h>
int a[21],flog=0,sum,n,vis[21];
int cmp(const void *c,const void *d)
{
	return *(int *)d-*(int *)c;
}
void dfs(int cur,int k,int l,int t)
{
	int i;
	if(cur==4)
	{
		flog=1;
		return ;
	}
	if(t>n-3)
		return ;
	for(i=k;i<n;i++)
	{
		if(flog)
			break;
		if(!vis[i]&&l<=sum)
		{
			vis[i]=1;
			l+=a[i];
			if(l==sum)
			{
				dfs(cur+1,1,0,1);
			}
			dfs(cur,i,l,t+1);
			vis[i]=0;
			l-=a[i];
		}
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	for(;T>0;T--)
	{
		int i;
		flog=0;
		sum=0;
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
			vis[i]=0;
		}
		if(sum%4)//木棒总长应为4的倍数
			printf("no\n");
		else
		{
			qsort(a,n,sizeof(a[0]),cmp);
			sum/=4;
			if(a[n-1]>sum)
				printf("no\n");
			else
			{
				dfs(1,0,0,1);
				if(flog==1)
					printf("yes\n");
				else
					printf("no\n");
			}
		}
		
	}
	return 0;
}

C++解答

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

int a[20], u[20], side, S, E;

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

int dfs(int s, int l, int k) {
	if (l == side) {
		k++;
		l = 0;
		s = S;
	}
	if (k == 4)
		return 1;
	for (int i = s; i <= E; i++)
		if (!u[i] && l + a[i] <= side) {
			u[i] = 1;
			if (dfs(i + 1, l + a[i], k))
				return 1;
			u[i] = 0;
		}
	return 0;
}

int main() {
	int n, m, i, k;
	scanf("%d", &n);
	while (n--) {
		scanf("%d", &m);
		for (side = i = 0; i < m; i++) {
			scanf("%d", &a[i]);
			side += a[i];
		}
		if (side % 4) {
			puts("no");
			continue;
		}
		side /= 4;
		sort(a, a + m, cmp);
		memset(u, 0, sizeof(u));
		for (S = k = i = 0; i < m; i++)
			if (a[i] > side)
				break;
			else if (a[i] == side) {
				k++;
				S = i + 1;
				u[i] = 1;
			}
		if (i < m) {
			puts("no");
			continue;
		}
		if (k == 3 || k == 4) {
			puts("yes");
			continue;
		}
		E = m - 1;
		if (dfs(S, 0, k))
			puts("yes");
		else
			puts("no");
	}
	return 0;
}