【练习】输出整数数组所有和为SUM的组合

int[] values = { 1, 3, 4, 5, 6, 15 };

15 = 1+3+5+6
15 = 4+5+6
15 = 15

import java.util.Arrays;
import java.util.Stack;

/**
 * 
 * @author wangmengjun
 *
 */
public class PrintAllByStack {

  /** 设定一个目标值 */
  public static final int TARGET_SUM = 20;

  /** 使用Stack存放已经使用的数值 */
  private Stack<Integer> stack = new Stack<Integer>();

  /** 存放当前Stack中元素的和 */
  private int sumInStack = 0;

  public void process(final int[] data, int target) {
    if (data == null || data.length == 0) {
      throw new IllegalArgumentException("data不能为空");
    }

    Arrays.sort(data);
    processRecursion(data, 0, data.length, target);
  }

  private void processRecursion(final int[] data, int fromIndex,
      int endIndex, int target) {

    if (sumInStack >= target) {
      if (sumInStack == target) {
        print(stack);
      }
      return;
    }

    for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {
      if (sumInStack + data[currentIndex] <= target) {
        stack.push(data[currentIndex]);
        sumInStack += data[currentIndex];
        /**
         * 从currentIndex +1开始继续递归
         */
        processRecursion(data, currentIndex + 1, endIndex, target);
        sumInStack -= (Integer) stack.pop();
      }
    }
  }

  /**
   * 打印符合条件的结果，如 15 = 4+6+5
   */
  private void print(Stack<Integer> stack) {
    StringBuilder sb = new StringBuilder();
    sb.append(TARGET_SUM).append(" = ");
    for (Integer i : stack) {
      sb.append(i).append("+");
    }
    System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
  }
}

/**
 * 
 * @author wangmengjun
 *
 */
public class Main {

  public static void main(String[] args) {
    PrintAllByStack example = new PrintAllByStack();
    int[] values = { 1, 4, 3, 6, 7, 9, 5, 8, 15, 16, 18, 17 };
    example.process(values, PrintAllByStack.TARGET_SUM);
  }

}

20 = 1+3+4+5+7
20 = 1+3+7+9
20 = 1+3+16
20 = 1+4+6+9
20 = 1+4+7+8
20 = 1+4+15
20 = 1+5+6+8
20 = 3+4+5+8
20 = 3+4+6+7
20 = 3+8+9
20 = 3+17
20 = 4+7+9
20 = 4+16
20 = 5+6+9
20 = 5+7+8
20 = 5+15

/**
 * @author wangmengjun
 *
 */
import java.util.Arrays;

public class PrintAllSubsets {

  /** 设定一个目标值 */
  public static final int TARGET_SUM = 20;

  public void process(final int[] data, final int target) {
    if (data == null || data.length == 0) {
      throw new IllegalArgumentException("data不能为空");
    }

    int len = data.length;
    /**
     * 处理前先排序一下，这样有一个好处，如果一个数添加进去已经大于target了，
     * 那么该数后面的数添加进去都将大于target
     */
    Arrays.sort(data);
    this.processRecursion(data, 0, new int[len], 0, target);
  }

  private void processRecursion(final int[] data, int fromIndex,
      final int[] stack, final int stacklen, final int target) {
    if (target == 0) {
      /**
       * 如果符合条件，则输出符合条件的情况
       */
      printResult(Arrays.copyOf(stack, stacklen));
      return;
    }

    while (fromIndex < data.length && data[fromIndex] > target) {
      /**
       * 借助数组已经排序的好处，后面更大的数值，只要增加索引即可。
       */
      fromIndex++;
    }

    while (fromIndex < data.length && data[fromIndex] <= target) {
      /**
       * 当数据用完，或者当数值大于剩余想获取的目标值，结束循环
       */
      stack[stacklen] = data[fromIndex];
      processRecursion(data, fromIndex + 1, stack, stacklen + 1, target
          - data[fromIndex]);
      fromIndex++;
    }
  }

  /**
   * 打印符合条件的结果，如 15 = 4+6+5
   */
  private void printResult(int[] copyOf) {
    StringBuilder sb = new StringBuilder();
    sb.append(TARGET_SUM).append(" = ");
    for (Integer i : copyOf) {
      sb.append(i).append("+");
    }
    System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
  }
}

/**
 * 
 * @author wangmengjun
 *
 */
public class Main {

  public static void main(String[] args) {
    PrintAllSubsets example = new PrintAllSubsets();
    int[] values = { 1, 4, 3, 6, 7, 9, 5, 8, 15, 16, 18, 17 };
    example.process(values, PrintAllSubsets.TARGET_SUM);
  }

}

20 = 1+3+4+5+7
20 = 1+3+7+9
20 = 1+3+16
20 = 1+4+6+9
20 = 1+4+7+8
20 = 1+4+15
20 = 1+5+6+8
20 = 3+4+5+8
20 = 3+4+6+7
20 = 3+8+9
20 = 3+17
20 = 4+7+9
20 = 4+16
20 = 5+6+9
20 = 5+7+8
20 = 5+15