DFS记忆模板题

深度优先遍历（DFS)是搜索的手段之一。它从某个状态开始，不断地转移状态直到无法转移，然后回退到前一步状态，继续转移到其他状态，如此不断反复，直到找到最终的解，和递归很像。

问题描述： 部分和问题
给定若干整数，判断是否可以从中选出若干个，是他们的和恰好为0

题解代码：

//输入
int a[MAX_N];
int n,k;

//已经从i项得到了和sum，然后对于i项之后的进行分支
bool dfs(int i,int sum) {
  //如果前n项都计算过了，则返回sum是否与k相等
 if(i==n) return sum==k;

 //不加上a[i]的情况
 if(dfs(i+1,sum)) return ture;

 //加上a[i]的情况
 if(dfs(i+1,sum+a[i]) return ture;

 //无论是否加上a[i]都不能凑成k就返回false
 return false;
 }

void solve(){
 if(dfs(0,0)) printf("Yes\n");
 else printf("No\n");
}

复杂度为O(2的n次方)