摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : DFS

須知:1.需要先排序來減少搜尋的次數
    2.把不可能的組合直接做判斷
    3.儘可能減少搜尋的次數...

/***********************************************************/

#include<stdio.h>
#include<stdlib.h>
int n,num[50],find;
int appear[50]={0};
void DFS (int now,int sum,int end,int start)
{
   int a;
   if(now==3) {find=1;return;}
   if(sum==end)    DFS(now+1,0,end,0);
   if(sum>=end||find==1) return;
   for(a=start;a<n;a++)
     if(appear[a]==0)
       {
         appear[a]=1;
         DFS(now,sum+num[a],end,a+1);
         appear[a]=0;
       }
}
main()
{
  int t,a,b,c;
  while(scanf("%d",&t)==1)
  while(t--)
     {
       scanf("%d",&n);
       int sum=0,max=0;
       for(a=0;a<n;a++)
            {
             scanf("%d",&num[a]);
             if(max<num[a]) max=num[a];
             sum=sum+num[a];
            }
       for(a=0;a<n;a++)
          {
            c=a;
             for(b=a+1;b<n;b++)
               if(num[b]>num[c]) c=b;
             int temp;
             temp=num[a];
             num[a]=num[c];
             num[c]=temp;
          }
            find=0;
            if(sum!=0&&sum%4==0&&max<=sum/4)
                 DFS(0,0,sum/4,0);
            if(find==1) printf("yes\n");
            else printf("no\n");
     }
 return 0;
}