回溯法解决子集和问题

* @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;
	}
   
}