数组(排列组合)追加求和限制值

数组(排列组合)累加求和限制值

  今日得闲，想起过往一朋友问到的一个排列组合问题，在数组中{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++;
                }
            }
        }
    }
}
/**
测试效果如下：
59
58
19
18
15
158
1
5
9
8
符合条件的个数：10
*/