正方形 - 计蒜客

题意分析：

搜索4条边，使得4条边满足相等而且等于sum/4，即数组所有元素一起能构成一个正方形

初代算法：

dfs(int id, int l1,int l2,int l3,int l4)
{
    dfs(id+1,l1+p[id],l2,l3,l4);
    dfs(id+1,l1,l2+p[id],l3,l4);
    dfs(id+1,l1,l2,l3+p[id],l4);
    dfs(id+1,l1,l2,l3,l4+p[id]);
}

对4条边进行搜索 会超时

分析：

每条边都是等效的，因此重复状态很多

不是很理解ac代码的k的作用.

#include <stdio.h>
#define MAXN 25
long long p[MAXN], n;
long long sum = 0;
long long a = 0;

int ok = 0;
long long vis[MAXN];
// x表示当前正在搜索第x(0,1,2)条边
// sum 表示当前搜索的边的长度
// k表示//避免重复状况（？）
// 即 若当前dfs的k仍从1开始，
// 遇到一个下标介于1和k之间的下标（记为j），
// 并且发现vis[j]=0，
// 那么其实已经说明j被这层dfs前面的dfs搜索过，
// 而且还不是正确答案状态，
// 可以省略这些状态，
// 所以每层k都要进行+1
void dfs(int sum,int k,int x)
{
    if(ok)
    {
        return;
    }
    if(x==3)
    {
        ok=1;
        return;
    }
    if(sum>a)
    {
        return;
    }
    if(sum==a)
    {
        dfs(0,0,x+1);
    }
    for(int i =k;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            dfs(sum+p[i],i+1,x);
            vis[i]=0;
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &p[i]);
        sum += p[i];
    }
    if(sum%4!=0)
    {
        printf("No");
        return 0; 
    }
    a = sum / 4;

    for(int i = 1;i<=n;i++)
    {
        if(p[i]>a)
        {
            printf("No");
            return 0;
        }
    }
    dfs(0,1,0);
    if (ok)
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
}