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

  今日得闲，想起过往一朋友问到的一个排列组合问题，在数组中{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 volatile String temp = "";

	private int[] arr = { 1, 5, 8, 9 };

	private volatile static int sum = 0;

	private volatile static List<String> list = new ArrayList<String>(64);//4 * 4 * 4 * 4

	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);
//		System.out.println(list.size());
	}

	/**
	 * 产生所有可能数据的排列组合 generateData
	 * 
	 * @param int count
	 * @param AccumulateArith
	 *            acc
	 * @return the void
	 */
	private void generateData(int count, AccumulateArith acc) {
		for (int i = 0, len = arr.length; i < len; 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, len = str.length(); i < len; 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();
//				quickSort(ch,0, ch.length -1);//faster sort 
				mergeSort(ch,0, ch.length -1);//merge sort
				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++;
				}
			}
		}
	}
	
	/**
	 * O(nlogn)
	 * @param a
	 * @param low
	 * @param high
	 */
	private static void quickSort(char[] a, int low, int high) {
		if (low < high) { // 如果不加这个判断递归会无法退出导致堆栈溢出异常
			int middle = getMiddle(a, low, high);
			quickSort(a, 0, middle - 1);
			quickSort(a, middle + 1, high);
		}
	}

	private static int getMiddle(char[] a, int low, int high) {
		char temp = a[low];// 基准元素
		while (low < high) {
			// 找到比基准元素小的元素位置
			while (low < high && a[high] >= temp) {
				high--;
			}
			a[low] = a[high];
			while (low < high && a[low] <= temp) {
				low++;
			}
			a[high] = a[low];
		}
		a[low] = temp;
		return low;
	}
	
	/**
	 * O(NlogN)
	 * @param a
	 * @param left
	 * @param right
	 */
	private static void mergeSort(char[] a, int left, int right) {
	      if(left<right){
	          int middle = (left+right)/2;
	          //对左边进行递归
	          mergeSort(a, left, middle);
	          //对右边进行递归
	          mergeSort(a, middle+1, right);
	          //合并
	          merge(a,left,middle,right);
	      }
	  }

	  private static void merge(char[] a, int left, int middle, int right) {
	      char[] tmpArr = new char[a.length];
	      int mid = middle+1; //右边的起始位置
	      int tmp = left;
	      int third = left;
	      while(left<=middle && mid<=right){
	          //从两个数组中选取较小的数放入中间数组
	          if(a[left]<=a[mid]){
	              tmpArr[third++] = a[left++];
	          }else{
	              tmpArr[third++] = a[mid++];
	          }
	      }
	      //将剩余的部分放入中间数组
	      while(left<=middle){
	          tmpArr[third++] = a[left++];
	      }
	      while(mid<=right){
	          tmpArr[third++] = a[mid++];
	      }
	      //将中间数组复制回原数组
	      while(tmp<=right){
	          a[tmp] = tmpArr[tmp++];
	      }
	  }
}
/**
 * 测试效果如下： 59 58 19 18 15 158 1 5 9 8 符合条件的个数：10
 */

 

2015-09-24