遡及法によるサブセットと問題の解決
1354 ワード
* @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;
}
}