bool dfs(int count,int pos,int res)这是本题中DFS算法的状态。三个要素 count （已经拼好的棍子个数），pos （现在遍历的第几根棍子），res （要凑成目标长度剩余的长度）
goal = sum/4;标记的数组我们定义为used[21].值为 true 则标记过，即用过了。值为 false 则未用过。
//声明，全局 bool used[21]; //初始化为false，main函数中 memset(used,false,sizeof(used));下面看DFS函数的代码：
bool dfs(int count,int pos,int res)
{
if(count==3)//3根拼好就能保证都拼好
return true;
for(int i=pos;i<t;i++)//DFS框架循环
{
if(used[i])//1
continue;
used[i] = true;//2
if(stick[i]==res)//3
{//DFS框架中的递归
if(dfs(count+1,0,goal))//4
return true;
}
else if(stick[i]<res)//5
{//DFS框架中的递归
if(dfs(count,i+1,res-stick[i]))//6
return true;
}
used[i] = false;//7
}
return false;
}//1：如果标记过就跳过下面过程#include <iostream>
#include <algorithm>
using namespace std;
bool used[21];
int stick[21];
int t,goal;
bool cmp(int a,int b)
{
return a>b;
}
bool dfs(int count,int pos,int res)
{
if(count==3)//3根拼好就能保证都拼好
return true;
for(int i=pos;i<t;i++)//DFS框架循环
{
if(used[i])
continue;
used[i] = true;
if(stick[i]==res)
{
if(dfs(count+1,0,goal))//DFS框架中的递归
return true;
}
else if(stick[i]<res)
{
if(dfs(count,i+1,res-stick[i]))//DFS框架中的递归
return true;
}
used[i] = false;
}
return false;
}
int main()
{
int n;
cin>>n;
while(n--)
{
cin>>t;
int sum=0;
for(int i=0;i<t;i++)
{
cin>>stick[i];
sum+=stick[i];
}
if(sum%4)
{
printf("no\n");
continue;
}
goal = sum/4;
memset(used,false,sizeof(used));
sort(stick,stick+t,cmp);
if(dfs(0,0,goal))//初始态
printf("yes\n");
else
printf("no\n");
}
return 0;
}原文：http://blog.csdn.net/guodongxiaren/article/details/23126997