hdu 1518 Square（DFS）

題目大意：所有的木棒連在一起，看能夠組成一個正方形

也是一道比較經典的DFS，剛做過hdu1455（1455題解:1455題解）那道題，方法都一樣，比這道難，現在做這道題感覺很easy

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,map[25],v[25];
int sum,length,flag;
bool cmp(int x,int y)
{
    return x > y;
}
void dfs(int num,int len,int pos)
{
    if(num == 4)
    {
        flag = 1;
        return;
    }
    if(flag) return;
    for(int i = pos ; i < n ; i ++)
    {
        if(v[i]) continue;
        if(map[i] + len == length)
        {
            v[i] = 1;
            dfs(num + 1,0,0);
            v[i] = 0;
        }
        else if(map[i] + len < length)
        {
            v[i] = 1;
            dfs(num,map[i] + len,i + 1);
            v[i] = 0;
            while(map[i] == map[i + 1])
            i++;
        }
    }
}
int main()
{
    int i,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        sum = 0 ;
        for(i = 0 ; i < n ; i ++)
        {
            scanf("%d",&map[i]);
            sum += map[i];
        }
        sort(map,map + n,cmp);
        if(sum%4)
        {
            printf("no\n");
            continue;
        }
        memset(v,0,sizeof(v));
        length = sum/4;
        flag = 0;
        dfs(1,0,0);
        if(flag) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}