Square

题意：给定n个长度不定的火柴，现在问能否通过这些火柴组成一个正方形；

解析：DFS搜索+剪枝；

搜索过程中，当搜到某一满足要求的火柴时，判断是否为第4根长度为某一值；如果是，则搜索完成；否则，将单次搜索单边完成，将临时记录单边长度的sum归0。

剪枝：

一、当火柴总和不能被4整除时，一定不能组成正方形，因此直接输出“no”;

二、当火柴中长度最长的一根火柴大于单边长度时，一定不能组成正方形，直接输出“no”;

三、当在搜索过程中，如果任意长度火柴的组成大于单边长度时，直接跳过搜索，会到上一起点进行搜索；

// 1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<cstring>
#include<string>
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;


const int maxn = 1005;

int num[ maxn ], vis[ maxn ], n, ave;
bool flag;

int cmp( int a, int b ){
	return a < b;
}

void Dfs( int sum, int cur, int step ){
	if( sum == ave ){
		step++;
		cur = 0;
		if( step == 4 ){
			flag = true;
		}
		else{
			sum = 0;
		}
	}
	if( flag ){
		return;
	}
	for( int i = cur; i < n; ++i ){
		if( !vis[ i ] ){
			if( sum + num[ i ] > ave )
				continue;
			vis[ i ] = 1;
			Dfs( sum + num[ i ], i, step );
			vis[ i ] = 0;
		}
	}
}

int main(){
	int Case, ans;
	cin >> Case;
	while( Case-- ){
		cin >> n;
		memset( vis, 0, sizeof( vis ) );
		ans = 0;
		flag = false;
		for( int i = 0; i < n; ++i ){
			cin >> num[ i ];
			ans += num[ i ];
		}
		sort( num, num + n, cmp );
		ave = ans / 4;
		if( ans % 4 ||	num[ n - 1 ] > ave ){
			puts( "no" );
			continue;
		}
		Dfs( 0, 0, 0 );
		if( flag ){
			puts( "yes" );
		}
		else{
			puts( "no" );
		}
	}
	return 0;
}

Square

原文：http://blog.csdn.net/bo_jwolf/article/details/19842853