一、问题简介 描述
子集和问题的一个实例为〈S,t〉。其中，S={ x1 ， x2 ，…，xn }是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得：SUM(S1) = c。
试设计一个解子集和问题的回溯法。
对于给定的正整数的集合S={ x1 ， x2 ，…，xn }和正整数c，计算S 的一个子集S1，使得：SUM(S1)=c。
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 二、问题分析 排列树回溯时间复杂度为 O(n!) 可通过加限制条件达到剪枝效果
三、代码 #include <iostream> using namespace std; int n=0,c=0; int d[10050]; int t[10050]; int l=0; int flag = 0; int mysum = 0; void backtrack(int,int,int); int main(){ //输入 cin>>n>>c; for (int i = 0; i < n; ++i) { cin>>d[i]; } //回溯调用 for (int i = 1; i <= n; ++i) { backtrack(i,0,n-1); if(flag == 1) break; } //输出 if (flag == 0){ cout<<"No Solution!"<<endl; } else{ for (int i = 0; i < l-1; ++i) { cout<<t[i]<<' '; } cout<<t[l-1]<<endl; } } void backtrack(int x,int s1,int s2){ if (x == 0){ if(mysum == c) flag = 1; //cout<<mysum<<endl; return; } for (int i = s1; i <= s2; ++i) { mysum += d[i]; t[l++] = d[i]; if (mysum<=c) //剪掉不可能的分支 backtrack(x-1,i+1,s2); if (flag == 1) //找到结果，退出 return; l--; mysum -= d[i]; } }