TJU 1398 Square DFS

**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, 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.

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
Output for Sample Input

yes
no
yes
**

题意：给出n条边，判断这些边是否能够组成正方形
思路：
剪枝部分：第一种情况：边长总长度必须是4的倍数
第二种情况：正方形边长必须大于最长的边
第三种情况：边的总数必须大于四条边
搜索部分：从最长的边依次往最短的边搜索，满足边长总长度为所需边长长度时才继续搜索满足下一条边的情况，用过一条边记得标记一下，如果凑齐了三条边，则必定有解。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int f[25],num[25];
int len,tn;
/*pos表示当前位置，l表示当前长度，count表示已找到的边长*/
int dfs(int pos,int l,int count)
{
    int i;
    /*只需要找到三条边即可*/
    if( count == 3)
        return 1;
    for( i = pos; i >= 1; i --)
    {
        /*用f数组记录该边长是否被找过*/
        if(!f[i])
        {
            f[i] = 1;
            /*如果没有达到边长的长度*/
            if( l+num[i] < len)
            {
                if(dfs(i-1,l+num[i],count))
                    return 1;
            }
            /*如果满足边长的长度*/
            else if( l+num[i] == len)
            {
                /*继续从最长边开始找，已找到的边长总数得加1*/
                if( dfs(tn,0,count+1))
                    return 1;
            }
            f[i] = 0;/*回溯，置为初始状态，便于下次搜索*/
        }
    }
    return 0;
}

int main()
{
    int t,i,sum;
    scanf("%d",&t);
    while( t--)
    {
        scanf("%d",&tn);
        sum = 0;
        memset(f,0,sizeof(f));
        for( i = 1; i <= tn; i ++)
        {
            scanf("%d",&num[i]);
            sum += num[i];
        }
        sort(num+1,num+tn+1);
        len = sum/4;
        /*剪枝，判断三种情况*/
        if( len*4!=sum||len < num[tn]||tn < 4)
        {
            printf("no
");
            continue;
        }
        /*从最长的边开始搜索*/
        if( dfs(tn,0,0))
        {
            printf("yes
");
        }
        else
            printf("no
");
    }
    return 0;
}

后记：这道题，哎，真是，错了9遍才过，剪枝漏掉了边长总数小于4的情况，搜索部分错在凑齐该条边以后应该重新从最长的边搜索。