原題鏈接：?[http://acm.hdu.edu.cn/showproblem.php?pid=1518](http://acm.hdu.edu.cn/showproblem.php?pid=1518)
**一：原題內容**
Problem Description
Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?
Input
The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.
Output
For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".
Sample Input
~~~
3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5
~~~
Sample Output
~~~
yes
no
yes
~~~
**二：理解分析**
給定一堆棍子，問是否能構造出一個正方形，當然所有棍子都要使用。首先判斷所有棍子長度是否能整除4，不能的話，肯定不是正方形，其次棍子中最長的那根，是否大于正方形的邊長呢？大于的話，當然也是不能組成正方形的。
**三：AC代碼**
~~~
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
bool visit[21];
int square[21];
int N;
int M;
int sum; //周長長度
int len; //邊長長度
bool flag; //標記是否已找到正方形
void DFS(int, int, int);
int main()
{
scanf("%d", &N);
while (N--)
{
scanf("%d", &M);
memset(visit, 0, sizeof(visit));
sum = 0;
flag = false;
for (int i = 0; i < M; i++)
{
scanf("%d", &square[i]);
sum += square[i];
}
sort(square, square + M);//排序
len = sum / 4;//求出邊長
if (sum % 4 == 0 && square[M - 1] <= len)//周長能整除4且所給長度的最大值小于等于邊長才有可能構造出正方形
DFS(0, M - 1, 0);
if (flag)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
void DFS(int sideLen, int k, int number)//sideLen代表當前正在構造的邊長長度；number標記當前已經有多少條邊構造出來了，當有三條邊已構造出來，那么根據正方形的性質，說明此時這些棍子是可以組成正方形的
{
if (sideLen == len)//已成功構造出一條邊長
{
number++;//這個地方起初是設置為全局變量（也就是DFS函數的第三參數起初是沒有的），但是交上去WA了，最后才發現是這里錯了。
sideLen = 0;
k = M - 1;
}
if (number == 3)//正方形已構造出
{
flag = 1;
return;
}
if (flag)
return;
for (int i = k; i >= 0; i--)
{
if (!visit[i] && square[i] + sideLen <= len)//如果這根棍子沒有使用過并且當前正在構造的邊長加上這個棍子的總長度也是不大于邊長的，那就可以了
{
visit[i] = 1;
DFS(sideLen + square[i], i - 1, number);
if (flag)
return;
visit[i] = 0;
while (square[i - 1] == square[i])
i--;
if (len - sideLen == square[i])
return;
if (sideLen == 0)
return;
}
}
}
~~~
參考鏈接：?[http://www.acmerblog.com/hdu-1518-Square-2075.html](http://www.acmerblog.com/hdu-1518-Square-2075.html)
