7-1 子集和问题 (50 分)
设集合S={x1,x2,…,xn}是一个正整数集合，c是一个正整数，子集和问题判定是否存在S的一个子集S1，使S1中的元素之和为c。试设计一个解子集和问题的回溯法。
输入格式:
输入数据第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。 是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。输出格式:
输出子集和问题的解，以空格分隔，最后一个输出的后面有空格。当问题无解时，输出“No Solution!”。
输入样例:
在这里给出一组输入。例如：
5 10
2 2 6 5 4
输出样例:
在这里给出相应的输出。例如：
2 2 6
本题要求只输出第一个解，并采用回溯法，所以可以主体来枚举所有情况，然后再剪枝剪掉不需要的分支：
package 宿題;
import java.io.*;
public class PTASubsetSum {
static int c;
static int n;
static boolean Out=true;//这里新建一个标记位，用来记录有无第一个解出现，结束递归；
public static void main(String args[])throws IOException{
StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));//当需要输入大量数据时BufferedReader处理速度快，比Scanner高效；
in.nextToken();
n=(int)in.nval;
in.nextToken();
c=(int)in.nval;
int a[]=new int[n];
int SUM=0;
for(int i=0;i<n;i++){
in.nextToken();
a[i]=(int)in.nval;
SUM+=a[i];//减去当所有数和小于c时的分支；
}
if(SUM>=c){
Count(a,0,0,"");
if(Out)
System.out.println("No Solution!");
}else
System.out.println("No Solution!");
}
private static void Count(int a[],int count,int sum,String s){
if(count<n&&Out){
if(sum+a[count]==c){
Out=false;//结束递归；
System.out.println(s+a[count]+" ");
}else if(sum+a[count]<c){//分支向下求解；
Count(a,count+1,sum+a[count],s+a[count]+" ");
System.out.println(s+a[count]+" ");
}
Count(a,count+1,sum,s);
System.out.println(s);
}
}
}
该算法最坏情形下时间复杂度为O(2^n)。
