数组(排列组合)累加求和限制值
? 今日得闲，想起过往一朋友问到的一个排列组合问题，在数组中{1,5,8,9}找出任意组合，所有数字之和累加值小于或等于14。? (即：不需要考虑顺序先后),列举所有的情况，并显示最终个数。现在提出一种思路，编码如下，抛砖引玉，探讨以资更好的方法。
import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.Iterator;import java.util.List;import java.util.Map;import java.util.Set;/** * 在数组中{1,5,8,9}找出任意组合，所有数字之和累加值小于或等于14。 * (即：不需要考虑顺序先后),列举所有的情况，并显示最终个数。 * @author Dennis Zhao * @createdTime：2012-5-24 * JDK 1.6.0_17 */public class AccumulateArith { private String temp = ""; private int[] arr = {1, 5, 8, 9}; private static int sum = 0; private static List<String> list = new ArrayList<String>(0); public static void main(String[] args) { for (int i = 0; i < 4; i++) { new AccumulateArith().generateData(i + 1, new AccumulateArith()); } filterCombination(list); System.out.println("符合条件的个数：" + sum); } /** * 产生所有可能数据的排列组合 * generateData * @param int count * @param AccumulateArith acc * @return the void */ private void generateData(int count, AccumulateArith acc) { for (int i = 0; i < arr.length; i++) { this.temp = acc.temp + arr[i]; if (count == 1) { //System.out.println(this.temp); //sum++; //去掉重复的 filterDuplicate(this.temp); } else if ( count > 1){ new AccumulateArith().generateData(count - 1, this); } else { continue; } } } /** * 去掉重复字符的 * filterDuplicate * @param String str * @return the void */ private void filterDuplicate(String str) { if (null != str && !"".equals(str.trim())) { Set<String> set = new HashSet<String>(0); String[] arr = new String[str.length()]; for (int i = 0; i < str.length(); i++) { arr[i] = (str.charAt(i) + ""); set.add(arr[i]); } if (set.size() > 0 && set.size() == str.length()) { list.add(str); //System.out.println(str); //sum++; } } } /** * 符合组合规则,无顺序 * filterCombination * @param List<String> sList * @return the void */ private static void filterCombination(List<String> sList) { if (null != sList && sList.size() > 0) { Map<String, String> map = new HashMap<String, String>(0); for (String str : sList) { char[] ch = str.toCharArray(); int i = 0 , k = 0; char temp; for (i = 0; i < ch.length; i++) { for (k = i + 1; k < ch.length; k++) { if (ch[i] > ch[k]) { temp = ch[i]; ch[i] = ch[k]; ch[k]= temp; } } } map.put(String.valueOf(ch), str); } Iterator<String> it = map.keySet().iterator(); for (; it.hasNext() ; ) { String str = it.next(); int accSum = 0; for (int i = 0; i < str.length(); i++) { accSum += Integer.parseInt(str.charAt(i)+ "") ; } if (accSum <= 14) { System.out.println(str); sum++; } } } }}/**测试效果如下：59581918151581598符合条件的个数：10*/?
?