首页 > 代码库 > 深度优先搜索
深度优先搜索
深度优先搜索（DFS， Depth-First Search）是搜索的手段之一。它从某个状态开始，不断地转移状态直到无法转移，然后退到前一步的状态，如此不断重复，直至找到最终的解。
部分和问题
给定整数a1、a2、……、an，判断是否可以从中选出若干个数，使它们的和恰好为k。
限制条件
- 1 ≤ n ≤ 20
- -108 ≤ ai ≤ 108
- -108 ≤ k ≤ 108
输入
n = 4
a = {1,2,4,7}
k =13
输出
Yes
从a1开始按顺序决定每个数加或不加，在全部n个数都决定后再判断它们的和是不是k即可。因为状态数是2n+1，所以复杂度是O(2n)。代码如下：
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 5 int n, k; 6 vector<int> a; 7 8 //已经从前i项得到了sum，然后对于i项之后的进行分支 9 bool dfs(int i, int sum)10 {11 //如果前n项都计算过了，则返回sum是否与k相等12 if (i == n) return sum == k;13 14 //不加上a[i]的情况15 if (dfs(i+1, sum)) return true;16 17 //加上a[i]的情况18 if (dfs(i+1, sum+a[i])) return true;19 20 //无论是否加上a[i]都不能凑成k就返回false21 return false;22 }23 24 int main()25 {26 while (cin >> n)27 {28 int tmp;29 for (int i = 0; i < n; i++)30 {31 cin >> tmp;32 a.push_back(tmp);33 }34 cin >> k;35 if (dfs(0, 0))36 cout << "Yes" << endl;37 else38 cout << "No" << endl;39 }40 return 0;41 }
深度优先搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。