子集和问题

http://www.iteye.com/topic/788198
数组a[]={3,5,2,4,1,8}，要求从a中找出所有“和”等于10的子集。
关于这个问题大家有什么看法，我能想到的就是遍历。
解法一：
Java代码 
public static void main(String[] args) {  
int a[]={3,5,2,4,1,8};  
int sub[]=new int[a.length];  
int SUM=10;  
for(int i=0;i<a.length;i++){  
    int res=a[i];  
    sub[0]=a[i];  
    int nextIndex=i+1;  
    for(int j=i+1;j<a.length;j++){  
        res+=a[j];  
        sub[j-nextIndex+1]=a[j];  
        if(res==SUM){  
            for(int x=0;x<=j-nextIndex+1;x++){  
                System.out.print(sub[x]+((x<j-nextIndex+1)?"+":""));  
            }  
            System.out.println("="+SUM);  
            j=nextIndex++;  
            res=a[i];  
            continue;  
        }else if(res>10){  
            j=nextIndex++;  
            res=a[i];  
            continue;  
        }  
    }  
}  
} 

public static void main(String[] args) {
int a[]={3,5,2,4,1,8};
int sub[]=new int[a.length];
int SUM=10;
for(int i=0;i<a.length;i++){
int res=a[i];
sub[0]=a[i];
int nextIndex=i+1;
for(int j=i+1;j<a.length;j++){
res+=a[j];
sub[j-nextIndex+1]=a[j];
if(res==SUM){
for(int x=0;x<=j-nextIndex+1;x++){
System.out.print(sub[x]+((x<j-nextIndex+1)?"+":""));
}
System.out.println("="+SUM);
j=nextIndex++;
res=a[i];
continue;
}else if(res>10){
j=nextIndex++;
res=a[i];
continue;
}
}
}
} 
3+5+2=10
3+2+4+1=10
5+4+1=10
2+8=10

解法二：
这个问题和什么硬币兑换的问题是同构的，用递归算法最简洁：

Java代码 
import java.util.Stack;  
 
public class SubsetCalc {  
 
    private int[] a = { 8, 5, 4, 3, 2, 1 };  
    private int sum = 10;  
    private Stack<Integer> stack = new Stack<Integer>();  
    private int stackSum = 0;  
 
    private void calc(int from, int to) {  
        if (stackSum == sum) {  
            for (Integer i : stack)  
                System.out.print(i + " ");  
            System.out.println();  
            return;  
        }  
 
        for (int i = from; i < to; i++) {  
            if (stackSum + a[i] <= sum) {  
                stackSum += stack.push(a[i]);  
                calc(i + 1, to);  
                stackSum -= stack.pop();  
            }  
        }  
    }  
 
    public void subsets() {  
        calc(0, a.length);  
    }  
 
    public static void main(String[] args) {  
        new SubsetCalc().subsets();  
    }  
} 

import java.util.Stack;

public class SubsetCalc {

private int[] a = { 8, 5, 4, 3, 2, 1 };
private int sum = 10;
private Stack<Integer> stack = new Stack<Integer>();
private int stackSum = 0;

private void calc(int from, int to) {
if (stackSum == sum) {
for (Integer i : stack)
System.out.print(i + " ");
System.out.println();
return;
}

for (int i = from; i < to; i++) {
if (stackSum + a[i] <= sum) {
stackSum += stack.push(a[i]);
calc(i + 1, to);
stackSum -= stack.pop();
}
}
}

public void subsets() {
calc(0, a.length);
}

public static void main(String[] args) {
new SubsetCalc().subsets();
}
} 

可以参考一个很经典的走台阶问题。我写了一份代码，如下：
Java代码 
public class Compositor {  
    
  static int[] a = { 8, 5, 4, 3, 2, 1 };  
    
  static int sum = 10 ;  
    
  public static void main(String[] args)  
  {  
    for(int i = 0 ; i < a.length ;i++)  
      subSet(new LinkedList<Integer>(), i);  
    }  
    
  public static void printResult(List<Integer> numList)  
  {  
    for(int i = 0 ; i < numList.size() ; i++)  
    {  
      if(i > 0)  
        System.out.print("+");  
      System.out.print(numList.get(i));  
    }  
    System.out.println("="+sum);  
  }  
    
  public static void subSet(List<Integer> numList,int start)  
  {  
      int curNum = a[start];  
        
      int total =  0 ;   
      for(int k = 0 ; k < numList.size() ; k++)  
      {  
        total += numList.get(k);  
      }  
        
      if(total + curNum == sum)  
      {  
        numList.add(curNum);  
        printResult(numList);  
      }  
        
      if(total + curNum < sum)  
      {  
        numList.add(curNum);  
        for(int i = start+1 ; i < a.length; i++)  
        {  
          List<Integer>  newList = new LinkedList<Integer>();  
          newList.addAll(numList);  
          subSet(newList,i);  
        }  
      }  
  }  
}