最近在学习递归，写了一个求组合的递归算法，仅供参考。
基本思想：求c(n,m)可以想像为从n-1个元素中找m-1个元素，每层选定一个元素并确定下来，最终简化为从剩余的元素中任意挑选一个元素，步骤如下。
假设求从5个数中任选3个数的组合：
设定一个指针p, 记录当前层选的是第几个元素
设定一个指针deep，记录当前是哪一层
每一层的选择元素的指针p依次向后移动，直到不能移到了为止。
import java.util.ArrayList; import java.util.List; /** *@author zjweii *@date 2011-2-16 *@desc */ public class C { private static List<int[]> dataList = new ArrayList<int[]>(); /** * @date 2011-2-16 * @param int[] data 一组数值。n * @param deep * 取几个数 m * @param p * 每层的当前元素的指针 * @param output * 收集每层挑选的元素，即组合输出 。 * @desc */ public static void cnm(int[] data, int deep, int p, int[] output) { while (p <= data.length - deep) { if (deep > 1) { //如果没到最后一层，继续挑。 output[deep-1] = data[p]; //每层挑一个元素 cnm(data, deep-1, ++p, output); //p始终指向上一层所挑元素的下一个元素 } else { //最后一层在剩余的元素中随便挑 while (p < data.length) { output[deep-1] = data[p++]; dataList.add(output); //保存输出到list里面 for (int i = output.length; i > 0; i--) System.out.print(output[i - 1] + " "); System.out.println(); } } } } public static void main(String[] args) { // TODO Auto-generated method stub int[] p = { 1, 2, 3, 4, 5,6,7,8,9,0 }; int r =5; int[] output = new int[r]; cnm(p, r, 0, output); System.out.println("Total:" + dataList.size()); } }
输出为：
1 2 3 4 5 1 2 3 4 6 1 2 3 4 7 1 2 3 4 8 1 2 3 4 9 1 2 3 4 0 1 2 3 5 6 1 2 3 5 7 1 2 3 5 8 1 2 3 5 9 1 2 3 5 0 1 2 3 6 7 1 2 3 6 8 1 2 3 6 9 1 2 3 6 0 1 2 3 7 8 1 2 3 7 9 1 2 3 7 0 1 2 3 8 9 1 2 3 8 0 1 2 3 9 0 1 2 4 5 6 1 2 4 5 7 1 2 4 5 8 1 2 4 5 9 1 2 4 5 0 1 2 4 6 7 1 2 4 6 8 1 2 4 6 9 1 2 4 6 0 1 2 4 7 8 1 2 4 7 9 1 2 4 7 0 1 2 4 8 9 1 2 4 8 0 1 2 4 9 0 1 2 5 6 7 1 2 5 6 8 1 2 5 6 9 1 2 5 6 0 1 2 5 7 8 1 2 5 7 9 1 2 5 7 0 1 2 5 8 9 1 2 5 8 0 1 2 5 9 0 1 2 6 7 8 1 2 6 7 9 1 2 6 7 0 1 2 6 8 9 1 2 6 8 0 1 2 6 9 0 1 2 7 8 9 1 2 7 8 0 1 2 7 9 0 1 2 8 9 0 1 3 4 5 6 1 3 4 5 7 1 3 4 5 8 1 3 4 5 9 1 3 4 5 0 1 3 4 6 7 1 3 4 6 8 1 3 4 6 9 1 3 4 6 0 1 3 4 7 8 1 3 4 7 9 1 3 4 7 0 1 3 4 8 9 1 3 4 8 0 1 3 4 9 0 1 3 5 6 7 1 3 5 6 8 1 3 5 6 9 1 3 5 6 0 1 3 5 7 8 1 3 5 7 9 1 3 5 7 0 1 3 5 8 9 1 3 5 8 0 1 3 5 9 0 1 3 6 7 8 1 3 6 7 9 1 3 6 7 0 1 3 6 8 9 1 3 6 8 0 1 3 6 9 0 1 3 7 8 9 1 3 7 8 0 1 3 7 9 0 1 3 8 9 0 1 4 5 6 7 1 4 5 6 8 1 4 5 6 9 1 4 5 6 0 1 4 5 7 8 1 4 5 7 9 1 4 5 7 0 1 4 5 8 9 1 4 5 8 0 1 4 5 9 0 1 4 6 7 8 1 4 6 7 9 1 4 6 7 0 1 4 6 8 9 1 4 6 8 0 1 4 6 9 0 1 4 7 8 9 1 4 7 8 0 1 4 7 9 0 1 4 8 9 0 1 5 6 7 8 1 5 6 7 9 1 5 6 7 0 1 5 6 8 9 1 5 6 8 0 1 5 6 9 0 1 5 7 8 9 1 5 7 8 0 1 5 7 9 0 1 5 8 9 0 1 6 7 8 9 1 6 7 8 0 1 6 7 9 0 1 6 8 9 0 1 7 8 9 0 2 3 4 5 6 2 3 4 5 7 2 3 4 5 8 2 3 4 5 9 2 3 4 5 0 2 3 4 6 7 2 3 4 6 8 2 3 4 6 9 2 3 4 6 0 2 3 4 7 8 2 3 4 7 9 2 3 4 7 0 2 3 4 8 9 2 3 4 8 0 2 3 4 9 0 2 3 5 6 7 2 3 5 6 8 2 3 5 6 9 2 3 5 6 0 2 3 5 7 8 2 3 5 7 9 2 3 5 7 0 2 3 5 8 9 2 3 5 8 0 2 3 5 9 0 2 3 6 7 8 2 3 6 7 9 2 3 6 7 0 2 3 6 8 9 2 3 6 8 0 2 3 6 9 0 2 3 7 8 9 2 3 7 8 0 2 3 7 9 0 2 3 8 9 0 2 4 5 6 7 2 4 5 6 8 2 4 5 6 9 2 4 5 6 0 2 4 5 7 8 2 4 5 7 9 2 4 5 7 0 2 4 5 8 9 2 4 5 8 0 2 4 5 9 0 2 4 6 7 8 2 4 6 7 9 2 4 6 7 0 2 4 6 8 9 2 4 6 8 0 2 4 6 9 0 2 4 7 8 9 2 4 7 8 0 2 4 7 9 0 2 4 8 9 0 2 5 6 7 8 2 5 6 7 9 2 5 6 7 0 2 5 6 8 9 2 5 6 8 0 2 5 6 9 0 2 5 7 8 9 2 5 7 8 0 2 5 7 9 0 2 5 8 9 0 2 6 7 8 9 2 6 7 8 0 2 6 7 9 0 2 6 8 9 0 2 7 8 9 0 3 4 5 6 7 3 4 5 6 8 3 4 5 6 9 3 4 5 6 0 3 4 5 7 8 3 4 5 7 9 3 4 5 7 0 3 4 5 8 9 3 4 5 8 0 3 4 5 9 0 3 4 6 7 8 3 4 6 7 9 3 4 6 7 0 3 4 6 8 9 3 4 6 8 0 3 4 6 9 0 3 4 7 8 9 3 4 7 8 0 3 4 7 9 0 3 4 8 9 0 3 5 6 7 8 3 5 6 7 9 3 5 6 7 0 3 5 6 8 9 3 5 6 8 0 3 5 6 9 0 3 5 7 8 9 3 5 7 8 0 3 5 7 9 0 3 5 8 9 0 3 6 7 8 9 3 6 7 8 0 3 6 7 9 0 3 6 8 9 0 3 7 8 9 0 4 5 6 7 8 4 5 6 7 9 4 5 6 7 0 4 5 6 8 9 4 5 6 8 0 4 5 6 9 0 4 5 7 8 9 4 5 7 8 0 4 5 7 9 0 4 5 8 9 0 4 6 7 8 9 4 6 7 8 0 4 6 7 9 0 4 6 8 9 0 4 7 8 9 0 5 6 7 8 9 5 6 7 8 0 5 6 7 9 0 5 6 8 9 0 5 7 8 9 0 6 7 8 9 0 Total:252
