錯(cuò)誤代碼，過不了的數(shù)據(jù)14：15 10 17 16 12 1 10 20 17 19 4 5 9 5  可能解：(20 15 5 ),(19 17 4 ),( 17 12 10 1 ), ( 16 10 9 5 )
下面的代碼“no”，因?yàn)?20 19 1),(17接下來(lái)湊不出來(lái) )
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
 int length[21];
 int mark[21];
 bool cmp(int x,int y)
{
    return x>y;
}

  int  dfs(int sum,int flag,int n,int time)//´Ótime¿ªÊ¼ËÑË÷
  {
  if(sum==0)return 1;
    if(time<n)
  {
   for(int k=time;k<n;k++)
   {
    if(mark[k]<0&&sum-length[k]>=0)
    {
     mark[k]=flag;
     if(dfs(sum-length[k],flag,n,k+1))
     return 1;
     else
     mark[k]=-1;
       } 
   }
  }
    
 return 0;
  }
  int main()
  {
  freopen("s.txt","r",stdin);
  freopen("key.txt","w",stdout);
  int num,n;
 
  cin>>num;
  while(num--)
  {
  int sum=0;
  cin>>n;
  for(int k=0;k<n;k++)
  {
   cin>>length[k];
   mark[k]=-1;
   sum+=length[k];
  }
  sort(length,length+n,cmp);
  if(sum%4!=0||length[0]>sum/4)
  cout<<"no"<<endl;
  else
  {
   sum/=4;
   if(dfs(sum,1,n,0))
    {
   if(dfs(sum,2,n,0))
          {
     if(dfs(sum,3,n,0))
     cout<<"yes"<<endl;
     else
     cout<<"no"<<endl;
        } 
        else
        cout<<"no"<<endl;
          }
         else
         cout<<"no"<<endl;
  }
    }
  //system("PAUSE");
  return   0;
  }
正確的解法應(yīng)當(dāng)是，在一起搜索。
下面是一段超時(shí)的代碼
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
 int length[21];
 int mark[21];
 int flag=0;
 int target;
 bool cmp(int x,int y)
{
    return x>y;
}

  int func(int i)
  {
  while(mark[i]>0)
  i++;
  return i;
 }
  void  dfs(int sum,int n,int time,int level)//從序號(hào)為time的開始搜索
  {
  if(flag)return ;
  if(sum==0&&level==3)
  {
  flag=1;
  return;
     }
     if(sum==0)
     {
   level++;
   dfs(target,n,func(0),level);
  }
    else if(time<n)
  {
   for(int k=time;k<n;k++)
   {
    if(k>1)
               {
               
                if(length[k]==length[k-1]&&!mark[k-1])
                    continue;//顯然
               }
                if(sum<length[n-1])  continue;//顯然
    if(mark[k]<0&&sum-length[k]>=0)
    {
     mark[k]=1;
     dfs(sum-length[k],n,func(k+1),level);
     mark[k]=-1;
       } 
   }
  }
  }
  int main()
  {
  freopen("s.txt","r",stdin);
  freopen("key.txt","w",stdout);
  int num,n;
 
  cin>>num;
  while(num--)
  {
  int sum=0;
  cin>>n;
  for(int k=0;k<n;k++)
  {
   cin>>length[k];
   mark[k]=-1;
   sum+=length[k];
  }
  sort(length,length+n,cmp);
  if(sum%4!=0||length[0]>sum/4)
  cout<<"no"<<endl;
  else
  {
   sum/=4;
   target=sum;
   dfs(sum,n,0,0);
       if(flag==0)
       cout<<"no"<<endl;
       else
       cout<<"yes"<<endl;
  }   
    }
  //system("PAUSE");
  return   0;
  }

上面超時(shí)就超時(shí)原因是減枝不徹底。level標(biāo)記也不太好
決定另外爐灶,先看看別人的代碼
#include<iostream>
#include<algorithm>
using namespace std;
int s[21];
int v[21];
int len;
int m;
int dfs(int cur,int num,int beg,int fin)
{    
 int solve(int );
 if(num==1)
  return 1;
 if(cur==len)
 {
  return solve(num-1);
 }
   for(int i=beg;i>=fin;i--)
   {
    if(!v[i]&&cur+s[i]<=len)
    {  
     v[i]=1;
     if(dfs(cur+s[i],num,i-1,fin))
      return 1;
     v[i]=0;
    }
   }
   return 0;
}

int solve(int edge_num)
{   
     int i;
  for(i=m;i>=1;i--)
   if(!v[i])
   { 
    v[i]=1;
    if(dfs( s[i],edge_num,i-1,1))
     return 1;
    v[i]=0;
   }
 return 0;
}

int main()
{
 int n;
 cin>>n;
 while(n--)
 {
  
  cin>>m;
  int i;
  int sum=0;
  for(i=1;i<=m;i++)
  {
   cin>>s[i];
   sum+=s[i];
   v[i]=0;
  }
  
  len=sum/4;
  if(4*len!=sum)
  {
   cout<<"no"<<endl;
   continue;
  }
  sort(s+1,s+m+1);
  if(s[m]>len)
  {
   cout<<"no"<<endl;
   continue;
  }
  if(solve(4))
   cout<<"yes"<<endl;
  else
   cout<<"no"<<endl;
 }
 return 0;
}//剪枝還可以做得更好！！！
人家的solve寫得好！！，結(jié)合dfs.