递归－组合（用背包问题解）

求指定数据的组合，这里的指定数据用一个数组模拟所有可以选择的数据

这个问题与背包问题解法相似，在任何一个时间点上可以将此问题划分为两个类似的子问题：组合中包含当前数据的，和组合中不包含当前数据的。

组合中包含当前数据的：在剩下的可选数据求得可能的n-1个元素的组合。

组合中不包含当前数据的：在剩下的可选数据求得可能的n个元素的组合。

组合可以看成另外一种背包问题 。

代码如下：求得5个数字中两个数字的组合。

class Combination {
	public static void main(String[] args) {
		int[] src = {2,4,8,6,10};
		select(src, 0, new int[src.length],2);
	}
	
	private static void select(int [] src, int offset, int[] bag,int n) {
		if(0 == n) {  //如果不需要寻找，则打印结果集合
			print(bag);
			return;
		}
		if(offset == src.length){ //如果没有寻找的范围，则直接退出
			return;	
		}
		select(src,offset+1,bag.clone(),n);	//在剩下的数字中找不包含当前位置的数据的组合
		select(src,offset+1,put(bag,src[offset]),n-1);	//在剩下的数字中找包含当前位置的数据的组合
	}
	
	private static int[] put(int[] bag, int n) { //将数字放入结果集合中
		int pos = -1;
		while(bag[++pos] > 0);	//找到结果集合中第一个数字为0的位置
		bag[pos] = n;
		return bag;
	}

	private static int getCount(int[] bag) {
		int result = bag.length;
		for(int i=bag.length - 1; i>=0; i--) {
			if(bag[i] == 0) result--;
			else return result;
		}
		return result;
	}

	private static void print(int[] bag) {	//打印结果集合中的数字
		System.out.print("bag: ");
		for(int n: bag) {
			if(n == 0) break;
			System.out.print(n + " ");
		}
		System.out.println();
	}
}