用layui做的网站/收录情况
NYOJ 1058 部分和问题 【DFS】
部分和问题
时间限制：1000 ms | 内存限制：65535 KB
难度：2
- 描述
- 给定整数a1、a2、.......an，判断是否可以从中选出若干数，使它们的和恰好为K。
- 输入
- 首先，n和k，n表示数的个数，k表示数的和。
接着一行n个数。
（1<=n<=20,保证不超int范围） 输出 - 如果和恰好可以为k，输出“YES”，并按输入顺序依次输出是由哪几个数的和组成，否则“NO” 样例输入
-
4 13 1 2 4 7
样例输出 -
YES
2 4 7
-
-
这里简单的Dp 其实 最开始最想的是怎么记录这个数据是否已经被计算了。。。 于是采用一个visit 数组记录 就可以将数字记录下来
-
实现代码：
#include<iostream> #include<cstdio> using namespace std; const int max_n = 1000; int k , n; int num ; int a[max_n]; int visit[max_n]; bool dfs(int i , int sum) {if(i == n) return sum == k;//如果不加这个数和就到达了K那么返回trueif(dfs(i + 1, sum)){visit[i] = 0;return true ;}//如果加上这个数和也k 那么返回trueif(dfs(i+1, sum + a[i])){visit[i] = 1;return true ;}return false; } void solve() {if(dfs(0, 0)){printf("Yes\n");for( int j = 0 ;j <= n ; j++){if(visit[j]){printf("%d ", a[j]);}}}else printf("No\n") ; } int main() {while(scanf("%d %d", &n, &k)== 2){num = 0;for(int i = 0 ; i < n ; i++){scanf("%d", &a[i]);}solve();}return 1; }
-
-
- 首先，n和k，n表示数的个数，k表示数的和。