#include <iostream>#include <algorithm>/*题目描述子集和问题的一个实例为〈S,t〉。其中，S={ 1 x ， 2 x ，…， n x }是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得s1中的各元素之和等于c。输入第一行有2个正整数n和c，n表示S的大小，c是子集子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。输出输出子集和问题的解，非下标，同时在n个数为升序的前提下，所出的子集顺序是唯一的。并输出共有几种组合，如果无解，则输出0注意，每个数字之间空2个空格，每行最后的数字也要空两个空格样例输入10 6030 46 86 5 11 66 84 49 69 55样例输出5 5511 492*/using namespace std;const int N = 1e5 + 10;int w[N], vis[N];int n, M;int ans;void SumOfSet(int s, int k) {// s为sum，前几个数的和if (k >= n) return;vis[k] = 1;if (s + w[k] == M) {for (int i = 0; i <= k; i++) {if (vis[i]) cout << w[i] << " ";}cout << endl;ans++;}else if (s + w[k] <= M) {SumOfSet(s + w[k], k + 1);}// k在退出上面的递归后，k已经加了1，之后和后面的数继续递归if (s + w[k + 1] <= M) {vis[k] = 0;SumOfSet(s, k + 1);}}int main() {// n:几个数// M:和数cin >> n >> M;for (int i = 0; i < n; i++) cin >> w[i];sort(w, w + n);SumOfSet(0, 0);cout << ans << endl;return 0;}
如果觉得《算法分析-子集和数 回溯法》对你有帮助，请点赞、收藏，并留下你的观点哦！
