一、题目描述：
【问题描述】子集和问题的一个实例为<S,M>。其中S={x1,x2,…,xn}是一个正整数的集合，M是一个正整数。找出S的所有子集S1，使得S1中所有元素的和为M。试设计一个解子集和问题的回溯法。
【样例输入】
5 10 12 13 15 18
30
【样例输出】
5 10 15
5 12 13
12 18
【样例说明】输入第一行是集合S,第二行是整数M;输出每一行代表一个解
二、设计思想
1、方法：递归+回溯
2、递归：back(i) 中含 back(i+1)
回溯：不放第i元素，继续 back(i+1)
3、back(i)主体：
（1）、if(i>n || Sum>SumFlag ||Num[i]>SumFlag) return; 跳出
（2）、满足条件，打印
（3）、放入第i元素，back(i+1)递归
Sum=Sum-Num[i];//回溯
不放入第i元素，back(i+1)递归
三、代码如下：
#include <bits/stdc++.h> #define N 100000 using namespace std; int n=6;//集合中元素个数 int Sum=0;//存目前计算的元素和 int SumFlag=0;//SumFlag值为所需求的元素和 int Num[N];//集合的元素 bool flag[N];//flag[i]=true表示放入计算，flag[i]=false表示未放入计算 void back(int i){ if(i>n || Sum>SumFlag ||Num[i]>SumFlag) return;//穷尽元素数组或者和大于SumFlag，跳出 //数组存储有数据的i最大值为n-1，将其放入flag数组为一次操作 //若其放入后，存储的元素满足题意，执行打印为一次操作使i=n //跳出为一次操作使i=n+1 //所以此次判断为i>n,而不是i>n-1 else if(Sum==SumFlag){//满足条件，输出 for(int i=0;i<n;i++){ if(flag[i]){ cout<<Num[i]<<" "; } } cout<<endl; } else{ Sum=Sum+Num[i]; flag[i]=true;//第i元素加入满足条件的元素组 back(i+1);//递归 Sum=Sum-Num[i];//回溯 flag[i]=false;//第i元素不加入满足条件的元素组 back(i+1);//递归 } } int main(){ for(int i=0;i<n;i++){//输入元素值 cin>>Num[i]; flag[i]=false;//将其对应的flag[i]设置为false } cin>>SumFlag;//SumFlag值为所需求的元素和 back(0); return 0; }
四、示例
1、示例输入：
5 10 12 13 15 18 30
2、示例输出：
5 10 15 5 12 13 12 18
