package com.haojia.algorithm;

import java.util.Random;

/**
 * 子集求和 非递归回溯 效率高
 * 
 * @author July
 * 
 */
public class SubSum {

    // 计算
    public static void compute(int[] data, int sum) {
        boolean[] state = new boolean[data.length];
        int p = 0;
        int temp = 0;
        int count = 0;

        while (true) {
            // 累加开始
            while (p != data.length) {
                if (!state[p]) {
                    state[p] = true;
                    temp += data[p];
                    if (temp == sum) {
                        count++;
                        print(data, sum, state);
                    }
                    if (temp > sum) {
                        state[p] = false;
                        temp -= data[p];
                    }
                }
                p++;
            }
            // 累加结束

            // 回溯开始
            while (state[p - 1]) {
                state[p - 1] = false;
                temp -= data[p - 1];
                p--;
                if (p == 0) {
                    System.out.println(count + "种方法");
                    return;
                }
            }

            while (!state[p - 1]) {
                p--;
                if (p == 0) {
                    System.out.println(count + "种方法");
                    return;
                }
            }

            state[p - 1] = false;
            temp -= data[p - 1];
            // 回溯结束
        }
    }

    // 格式化打印
    public static void print(int[] data, int sum, boolean[] state) {
        StringBuffer s = new StringBuffer();
        for (int i = 0; i < data.length; i++) {
            if (state[i]) {
                s.append(data[i]);
                s.append("+");
            }
        }
        System.out.println(s.substring(0, s.length() - 1) + "=" + sum);
    }

    public static void main(String[] args) {
        Random r = new Random();
        int[] data = new int[20];
        for (int i = 0; i < data.length; i++) {
            data[i] = r.nextInt(100);
        }
        compute(data, 100);
    }
}

------解决方案--------------------

Java code
package cxz.math;

import java.util.Calendar;

public class Cal {
  int[] data = { 5, 5, 5, 5, 20, 20, 20, 20, 10, 10, 10, 5, 5, 10, 10, 20, 20, 10, 10, 5 };
  int total = 100;
  /////////////////
  int nt = data.length;
  int[] s = new int[nt];
  int m[] = { 1, 0 };
  int fm = 0;
  int no = 0;

  public static void main(String[] args) {
    Calendar cstart = Calendar.getInstance();
    Cal g = new Cal();
    g.cal();
    Calendar cend = Calendar.getInstance();
    System.out.println("花费时间" + (cend.getTimeInMillis() - cstart.getTimeInMillis()) / 1000.0 + "秒");
  }

  public void cal() {
    fm = 0;
    f(0);
  }

  private void f(int n) {
    if (n == nt) {
      return;
    }
    for (int i = 0; i < m.length; i++) {
      s[n] = m[i];
      if (m[i] == 1) {
        fm += data[n];
        if (fm == total) {
          no++;
          show();
        }
      }
      if (fm < total)
        f(n + 1);
      if (m[i] == 1) {
        fm -= data[n];
      }
    }
  }

  void show() {
    StringBuffer buf = new StringBuffer();
    for (int L = 0; L < data.length; L++)
      buf.append((s[L] == 1 ? (data[L] + " ") : ""));
    System.out.println(no + ":" + buf.toString());
  }
}