子集和问题代码二

利用dfs实现 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 子集和问题的一个实例为〈S,t〉。其中，S={ x1 ， x2 ，…，xn }是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得： 。 试设计一个解子集和问题的回溯法。 对于给定的正整数的集合S={ x1 ， x2 ，…，xn }和正整数c，计算S 的一个子集S1，使得： 。 Input 输入数据的第1 行有2 个正整数n 和c（n≤10000，c≤10000000），n 表示S 的大小，c是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。 Output

将子集和问题的解输出。当问题无解时，输出“No Solution!”。 Sample Input

5 10 2 2 6 5 4

Sample Output

2 2 6

#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; int main() { int n, m; cin >> n >> m; int num[10010]; int v[10010]; memset(v, 0, sizeof(v)); for (int i = 0; i < n; i++) { cin >> num[i]; } int x = 0; int an[10010]; int to = 0, sum = 0; while (x >= 0) { if (v[x] == 0) { v[x] = 1; an[to++] = num[x]; sum += num[x]; if (m == sum) { for (int i = 0; i < to; i++) { if (i == to - 1) printf("%d\n", an[i]); else printf("%d ", an[i]); } return 0; } else if (sum > m) { v[x] = 0; sum -= num[x]; to--; } x++; } if (x >= n) { while (v[x - 1] == 1) { x--; v[x] = 0; if (x < 1) { printf("No Solution!\n"); return 0; } } while (v[x - 1] == 0) { x--; if (x < 1) { printf("No Solution!\n"); return 0; } } sum -= num[x - 1]; to--; v[x - 1] = 0; } } return 0; }