日期:2014-05-20 浏览次数:21138 次
public static void main(String[] args) { List<List<Integer>> re = op(1, 5, 3, 3); if (re == null) { System.out.println("error"); return; } for (List<Integer> tl : re) { for (Integer n : tl) { System.out.print(n + ","); } System.out.println(""); } } static List<List<Integer>> op(final int min, final int max, final int age, final int count) { List<List<Integer>> tn = new ArrayList<List<Integer>>(); {//初始化 int sum = age * count; //确定最大边界 int bmax = sum - min * (count - 1); bmax = Math.min(bmax, max); //最小边界 int bmin = sum - max * (count - 1); bmin = Math.max(bmin, min); if (bmax < bmin) { return null; } for (int i = bmin; i <= bmax; i++) { List<Integer> nl = new ArrayList<Integer>(); nl.add(i); tn.add(nl); } } for (int i = 1; i < count; i++) { List<List<Integer>> btn = new ArrayList<List<Integer>>(); for (int j = 0, jm = tn.size(); j < jm; j++) { List<Integer> nl = tn.get(j); int sum = count * age; for (Integer item : nl) { if (item == null) { break; } sum -= item; } //确定最大边界 int bmax = sum - min * (count - i - 1); bmax = Math.min(bmax, max); //最小边界 int bmin = sum - max * (count - i - 1); bmin = Math.max(bmin, min); for (int z = bmin; z <= bmax; z++) { List<Integer> bnl = new ArrayList<Integer>(); bnl.addAll(nl); bnl.add(z); btn.add(bnl); } } tn = btn; } //排序 for (List<Integer> l : tn) { Collections.sort(l); } Collections.sort((List) tn, new Comparator<List<Integer>>() { public int compare(List<Integer> o1, List<Integer> o2) { for (int i = 0; i < o1.size(); i++) { if (!o1.get(i).equals(o2.get(i))) { return o1.get(i) - o2.get(i); } } return 0; } }); //去重复 for (int i = 1; i < tn.size(); i++) { List<Integer> a = tn.get(i - 1); List<Integer> l = tn.get(i); if (a.get(0).equals(l.get(0))) { if (a.containsAll(l) && l.containsAll(a)) { tn.remove(i); i--; } } } return tn; }
------解决方案--------------------
public static void test4(int[] array, int begin, int num, int cVal, int val, List<Integer> result) { if (result.size()==num) { if (cVal==val) { System.out.println(result); } return; } for (int i = begin; i<array.length; i++) { if (cVal<val&&result.size()<num) { result.add(array[i]); cVal += array[i]; test4(array,i+1, num, cVal, val, result); cVal -= result.remove(result.size()-1); } } } public static void main(String[] args) { int[] array = { 1, 2, 3, 4 ,5,6,7,8,9}; test4(array, 0, 3, 0, 11, new ArrayList()); }