关于DFS心得：

1、利用结构体，记录mark和题目要求的基本属性。

2、用到递归，使用递归时注意要设置出口，即符合要求时return，注意对递归的理解，对于不同情况可能要传递不同的参数，但出口都是一样的。

3、在DFS时可以剪枝，即对明显不符合条件的情况（基本判断，比如正方形的四边一样长，三角形的两边大于第三边）直接排除，不参与递归，在剪枝的时候注意正确的剪枝。所以在DFS超时时可以考虑剪枝。

4、在递归发现不符合条件需要返回上一层的时候，要将不符合条件的元素flag消除（DFS、BFS的区别之一）。

例题：

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 11 20 30 40 50

8 1 7 2 6 4 4 3 5

.

Sample Output

yes

no

yes

大神滴代码。。。。。。。。。。。。

//剪支62MSAC#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int n,cnt,sum;struct node{ int lenth; int mark;}stick[25];int cmp(node a,node b){ return a.lenth>b.lenth;}int dfs(int len,int count,int l,int pos){ if(count==4)return 1; for(int i=pos;i
           
            (stick[i].lenth+l)) { stick[i].mark=1; l+=stick[i].lenth; if(dfs(len,count,l,i+1)) return 1; l-=stick[i].lenth; stick[i].mark=0; if(l==0) return 0; while(stick[i].lenth==stick[i+1].lenth)i++; } } return 0;}int main(){ int T; cin>>T; while(T--) { scanf("%d",&n); cnt=sum=0; for(int i=0;i
            
             #include 
             
              using namespace std;int n,s,k,a[22],visit[22]={ 0};? //a数组用来记录那一组数据，visit数组用来记录当前组的数据是否可用void DFS(int sum,int x,int d)? //sum是当前计算的和，等于正方形边长的话就配好了一条边了，x是记录当前配好了多少条边，d是上一次匹配到了哪里，是剪枝的关键{ if(k||x==3)? //当配上了三边的时候就说明能构成正方形了，如果已经能配成正方形就直接返回了 { k=1;return;? //k=1标记已经能够成正方形了 } int i; for(i=d;i
              
               >m; while(m--&&cin>>n) { for(i=s=0;i
               
                >a[i],s+=a[i];? //统计正方形周长 sort(a,a+n,cmp);? //从小到大排序 if(s%4==0)? //判断周长是否是正方形的形式 { s/=4;? //s变成记录正方形的边长 k=0;? //初始化k DFS(0,0,0);? //和为0，已配成的边数量为0，断点是起点 if(k)cout<<"yes"<