题目描述：
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
代码如下：
1 /*要剪枝，当所有木棒总长度不能被4整除时以及木棒最大长度大于总长度除以4时， 2 * 不能组成正方形，直接输出no 3 * 深搜时从第一个开始往后搜索，只要满足当前边长+当前木棒长 <正方形边长， 4 * 就标记该木棒，并继续搜索后面的木棒，当木棒长度="sum/4" 时，count加1， 5 当count="3时表明能够成正方形，flag=1，返回，flag=0则不能组成正方形。*/" 6 #include7 #include 8 9 int visit[20];10 bool flag;11 int number[20];12 int n,len;13 14 using namespace std;15 16 void dfs(int cur,int pos,int count);17 int main()18 {19 int m;20 cin >> m;21 while(m--)22 {23 int max = 0,sum = 0;24 cin >> n;25 memset(visit,0,sizeof(visit));26 for(int i = 0;i < n;i++)27 {28 cin >> number[i];29 sum += number[i];30 if(number[i] > max)31 max = number[i];32 }33 len = sum / 4;34 if(sum % 4 != 0 || max > len)//不能总和不能被4整除或最大值大于平均值35 {36 cout << "no" << endl;37 continue;38 }39 flag = 0;40 dfs(0,0,0);41 if(flag)42 cout << "yes" << endl;43 else44 cout << "no" << endl;45 }46 }47 48 void dfs(int cur,int pos,int count)49 {50 if(cur == len)//木棍相加的值等于平均值51 {52 count++;53 cur = 0;//当一边成立时，要考虑另外一边注意将cur清054 pos = 0;55 if(count == 3)//当有三边成立时56 {57 flag = 1;58 return;59 }60 }61 for(int i = pos;i < n;i++)62 {63 if(!visit[i])//还没有被访问过64 {65 if((cur + number[i]) <= len)//加上木棍后，长度小于或等于平均值66 {67 visit[i] = 1;68 dfs(cur + number[i],i,count);69 if(flag)//一旦有成立的，跳过剩下的判断70 return;71 visit[i] = 0;//回溯72 }73 }74 }75 }
代码分析：
这道题目要注意的地方就是剪枝。
参考地址：