Square
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9502 Accepted Submission(s): 3091
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 1005
int m;
int a[maxn];
int ss;
bool vis[maxn];
bool flag;
void dfs(int dep,int sum,int cnt){
if(sum>ss)return ;
if(sum==ss){
dep=0;
cnt++;
sum=0;
if(cnt==3){flag=1;return;}
}
if(flag)return ;
for(int i=dep;i<m;i++){
if(flag)return;
if(!vis[i]){
vis[i]=1;
dfs(i,sum+a[i],cnt); //一開始第一個參數寫成了dep+1,結果一直tle
vis[i]=0;
if(flag)return;
//while(a[i]==a[i+1]&&i<m)i++;
}
}
}
int main()
{
int n;
//freopen("in.txt","r",stdin);
scanf("%d",&n);
while(n--){
scanf("%d",&m);
ss=0;
memset(vis,0,sizeof vis);
for(int i=0;i<m;i++){
scanf("%d",&a[i]);
ss+=a[i];
}
flag=0;
if(ss%4!=0)puts("no");
else{
ss=ss/4;
dfs(0,0,0);
if(flag==0)puts("no");
else puts("yes");
}
}
}