题目表述

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?
输入：
The first line of input contains N, tlie 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 10000.
输出:
For each case, output a line containing “yes” if is is possible to form a square; otherwise output “no”.
样例输入:
3
31111
410 20 30 40 50
8 1 7 2 6 4 4 3 5
样例输出：
yes
no
yes

算法（深度优先搜索+剪枝）

思路

【题目大意】
给出一堆长度各异的木棍，这些木棍能否头尾相连形成一个正方形?
【分析】
题面要求判断能否搜索出一个方案让这些木棍形成正方形。首先，将木棍长度进行累加，得到总长length;然后将length除以4得到正方形的边长side;之后，将木棍拼凑成长度为side的边，拼凑完一条边后，再拼凑下一条，直到拼凑出4条长度为side 的边，从而构成一个正方形。
搜索状态三元组(sum, number, position)，其中 sum是当前拼凑的木棍长度，number是已拼凑成边长的数量, position是当前木棍的编号。需要搜索到的目标状态为number=3。
为什么不是4呢?因为如果总长length能够整除4，且已经拼凑出3条边，那么剩下的木棍必定可以构成最后的一条边。由于从第一根木棍开始拼凑，故搜索初始状态为(0,0,0)。
在搜索过程中，可以通过放弃对某些不可能产生结果的子集的搜索，达到提高效率的目的。这样的技术称为剪枝。
sum是当前拼凑的木棍长度，number是已拼凑成边长的数量, position是当前木棍的编号。需要搜索到的目标状态为number=3。
剪枝：
1.从大到小搜索，sort排序
2.能否除断4=side
3. 某根长度大于side，不符合 ，当前最长木棍必须用来组边。
4.当前边所搜索到的一个边不符合，相同边均不搜索，对相同长度木棍分类，避免搜索的时候做重复的搜索。
5.最后一条边不用搜，number=3则成功
6.记录当前所到木棍的序号，即为代码中的position
7.number==3，即搜索完毕

C++代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=25;
int n,m,side,len;
int b[MAXN];
bool visit[MAXN];

bool dfs(int sum,int number,int position) {
    if(number==3) { //剪枝7
        return true;
    }
    int sample=0;
    for(int i=position; i<m; i++) {
        if(visit[i]||sample==b[i]||sum+b[i]>len) {//剪枝4
            continue;
        }
        visit[i]=true;
        if(sum+b[i]==side){//边构建成功 
            if(dfs(0,number+1,0)){//继续重新搜索下一边 
                return true;
            }else{
                sample=b[i];//剪枝4
            }
        }else{//继续搜索构建当前边 ，从下一个木棍position开始 
            if(dfs(sum+b[i],number,i+1)){//剪枝6
                return true;
            }else{
                sample=b[i];
            } 
        }
        visit[i]=false;
    }
    return false;
}
bool cmp(int x,int y) {
    return x>y;
}
int main() {
    cin>>n;
    while(n--) {
        cin>>m;
        len=0;
        for(int i=0; i<m; i++) {
            scanf("%d",&b[i]);
            len+=b[i];
        }
        if(len%4!=0) {//剪枝2 
            cout<<"no"<<endl;
            continue;
        }
        memset(visit,false,sizeof(visit));
        side=len/4;
        sort(b,b+m,cmp);//剪枝1
        if(b[0]>side) { //剪枝3
            cout<<"no"<<endl;
            continue;
        }
        if(dfs(0,0,0)) {
            cout<<"yes"<<endl;
        } else {
            cout<<"no"<<endl;
        }
    }
    return 0;
}