子集和问题
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);
}
}
}
}