回溯法解决子集和问题
* @author chenzhuzuo * @version2011.06.24 * 回溯法求子集和 * */public class SubSum {/** * @param args */public static void main(String[] args) {int a[]= new int []{1,2,3,4,5,6};getSum(a,6);}private static void getSum(int arr[],int sum){int len= arr.length;int s[] = new int[len+1];for(int i=0;i<=len;i++){s[i]=0;}int k=1;while(k>=1){s[k]=1;if(sum==sum(arr,k,s)){for(int i=1;i<=k;i++){if(s[i]==1)System.out.println(arr[i-1]);}return;}else if(sum>sum(arr,k,s)){k++;}else{s[k]=0;k++;}if(k>len){while(s[k-1]==1){s[k-1]=0;k--;}while(s[k-1]==0){k--;if(k<1){System.out.println("result not found");return;}} s[k-1]=0;}}}private static int sum(int[] arr, int k,int []s) {int sum=0;for(int i=1;i<=k;i++){if(s[i]==1)sum+=arr[i-1];}return sum;} }