首页 > 其他 > 详细

NYOJ-1058 DFS部分求和

时间:2019-03-01 10:15:04      阅读:232      评论:0      收藏:0      [点我收藏+]

 原题链接

本题思路:暴力深搜,具体见代码。

 1 #include <iostream>
 2 #include <stack>
 3 using namespace std;
 4 
 5 const int maxn = 20 + 5;
 6 int a[maxn];
 7 int n, k;
 8 bool flag;
 9 stack <int > s;
10 
11 bool dfs(int i, int sum) {
12     if(i == n) return sum == k;//当搜到最后一个数时返回sum == k
13     if(dfs(i + 1, sum))  return true;//不加这个数的情况
14     if(dfs(i + 1, sum + a[i])) {//如果添加这个数满足k == sum 则将这个数加入栈中
15         s.push(a[i]);
16         return true;
17     }
18     return false;
19 }
20 
21 int main () {
22     while(cin >> n >> k) {
23         flag = true;
24         if(n == 0)  break;
25         for(int i = 0; i < n; i ++)
26             cin >> a[i];
27         flag = dfs(0, 0);
28         if(flag) {
29             cout << "YES" << endl;
30             while(!s.empty()) {
31                 cout << s.top() << " ";
32                 s.pop();
33             }
34         } else cout << "NO" << endl;
35     }
36     return 0;
37 }

 

NYOJ-1058 DFS部分求和

原文:https://www.cnblogs.com/bianjunting/p/10454749.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!