给定数量的1、5、10三种面值的货币，对于某个给定的总数（例

package test;

import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 给定数量的1、5、10三种面值的货币，对于某个给定的总数（例如10），可以有多少种可能的组合方案。 输入样例： 5 2 1 10
 * 解释：第一行三个数字，依次表示1、5、10三种面值货币的数量；第二行一个数字，表示给定的总数
 * 
 * 输出样例： 3 解释：针对上面输入，10有三种组合方式：1*5+5*1，5*2，10*1
 * 
 * @author Administrator
 *
 */
public class TestSU2 {

  static final Integer[][] array = {{1, 5000}, {5, 5000}, {10, 5000}};

  static final int target = 5000;

  public static void main(String[] args) {
    long start = System.currentTimeMillis();
    combinationSum(Arrays.asList(array), target);
    long end = System.currentTimeMillis();
    System.out.println("cost " + (end - start) + "ms.");
  }

  /**
   * combinationSum
   * 
   * @param nums
   * @param target
   * @return
   */
  public static List<Map<Integer, AtomicInteger>> combinationSum(List<Integer[]> nums, int target) {
    List<Map<Integer, AtomicInteger>> result = new LinkedList<>(); // 最终结果
    Map<Integer, AtomicInteger> intermediate = new LinkedHashMap<>();
    dfs(nums, target, 0, intermediate, result);
    return result;
  }

  /**
   * 
   * @param nums
   * @param gap
   * @param level
   * @param intermediate
   * @param result
   */
  private static void dfs(List<Integer[]> nums, int gap, int level,
      Map<Integer, AtomicInteger> intermediate, List<Map<Integer, AtomicInteger>> result) {
    if (gap == 0) { // 找到一个合法解
      System.out.println("===================答案=====================");
      intermediate.entrySet().stream().filter(m -> m.getValue().get() != 0).forEach(m -> {
        System.out.println(String.format("面值纸币:%s, 数量:%s.", m.getKey(), m.getValue().get()));
      });
      return;
    }

    for (int i = level; i < nums.size(); i++) { // 扩展状态
      int item = nums.get(i)[0];
      int limit = nums.get(i)[1];

      AtomicInteger count = intermediate.get(item);
      // System.out.println("gap:" + gap + ",item:" + item + ", value:"
      // + String.valueOf((count == null) ? 0 : count.get()));
      if (((count == null) ? 0 : count.get()) >= limit) {
        continue;
      }

      if (gap < item) {
        return; // 剪枝
      }

      if (intermediate.get(item) == null) {
        intermediate.put(item, new AtomicInteger(1));
      } else {
        intermediate.get(item).incrementAndGet(); // 执行扩展动作
      }

      dfs(nums, gap - item, i, intermediate, result);
      if (intermediate.get(item) != null) {
        intermediate.get(item).decrementAndGet();
      } // 撤销动作
    }
  }


}