一个关于组合数的问题

1. 题目来源 未解之谜俱乐部

import java.util.ArrayList;
import java.util.List;

/**
 *@date   2010-5-3 下午05:50:30
 *@author dycc
 *@file   NumberMystery.java
 *@desc   给定集合 A = [31,37,8,81,34,39,56,5,41,22,28,67],
 *        以及 x + y + z = 99,其中 x,y,z 属于集合A,
 *        问 x = ?,y = ?,z = ?
 */
public class NumberMystery {
	/**
	 * main 方法
	 * @param args
	 */
	public static void main(String[] args) {
	    Integer[] array = {31,37,8,81,34,39,56,5,41,22,28,67};
	    // step1 对原始数组进行排序
	    swapSort(array);
	    // step2 计算组合数(排列组合)
	    List<Integer[]> list = getGroup(array, 0, 3);
	    // step3 输出结果
	    for(int i=0;i<list.size();i++){
	    	Integer[] arr = list.get(i);
	    	if(sumArray(arr) == 99){
	    		printArray(arr);
	    	}
	    }
	    System.out.println("--- ok ---");
    }
	/**
	 * 交换排序
	 * @param array 原始数组
	 * @return
	 */
	public static Integer[] swapSort(Integer[] array){
		if(array == null || array.length < 2){
			return array;
		}
		// [0,array.length-2]
		for(int i=0;i< array.length - 1;i++){
			// find the min number in [i+1,array.length-1]
			int min = i;
			for(int j= i+1;j<array.length;j++){
				if(array[j] < array[min]){
					min = j;
				}
			}
			if(min > i){
				int tmp = array[i];
				array[i] = array[min];
				array[min] = tmp;
			}
		}
		return array;
	}
	/**
	 * 以 size 为单位进行组合
	 * @param data  原始数据
	 * @param start 起始下标
	 * @param size  组合大小
	 * @return
	 */
	public static List<Integer[]> getGroup(Integer[] data,int start,int size){
		List<Integer[]> list = new ArrayList<Integer[]>();
		// 非法入参
		if(data == null || start < 0 
				|| (data.length - start) < size){
			return list;
		}
		// 计算 size==1 的组合
		if(size == 1){
			for(int i=start;i<data.length;i++){
				list.add(new Integer[]{data[i]});
			}			
			return list;
		}
		// 计算组合数
		for(int i=start;i<data.length - (size-1);i++){			
			List<Integer[]> subList = getGroup(data, i + 1, size - 1);
			for(int j=0;j<subList.size();j++){
				Integer[] item = new Integer[size];
				item[0] = data[i];
				Integer[] subItem = subList.get(j);
				for(int k=0;k<size-1;k++){
					item[k+1] = subItem[k];					
				}
				list.add(item);
			}
		}
		return list;
	}
	/**
	 * 计算数组的和
	 * @param arr
	 */
	public static int sumArray(Integer[] arr){
		int sum = 0;
		for(int i=0;i<arr.length;i++){
			sum += arr[i];
		}
		return sum;
	}
	/**
	 * 打印数组
	 * @param arr
	 */
	public static void printArray(Integer[] arr){
		for(int i=0;i<arr.length;i++){
			System.out.print(arr[i]);
			if(i < arr.length -1){
				System.out.print(",");
			}
		}
		// 换行
		System.out.println();
	}
}

 

2.