组合的递归算法Java实现过程

一、无重复项的组合
 对于无重复项的组合问题的递归思路可从以下几个步骤入手（以数组为例，如对其他元素排列，将元素编号放入数组即可）：

 以数组a[5]={1,2,3,4,5}为例，用C(5,num)表示从这5个数中选择num个数，求其所有的情况。

 首先要明确，求一组数的组合问题，元素是没有位置要求的，即对于C(5,3)的求解{1,2,3}和{3,2,1}是一种情况。因此，为了防止结果的多余项，必须保证在求解过程中，原数组的元素位置是固定的！

 1、选取一个元素，即求解C(5,1)时，按序号从数组中顺序取出一个元素，结果为{1}  {2}  {3}  {4}  {5}

 2、选取两个元素，即求解C(5,2)时，先按序号从数组中顺序取出一个元素，再在取出的元素后面的元素中选取一个元素。设这个序号为i，则当i=5-2=3时为止（i从0开始），因为当i>3时，后面的元素不足1个。详细如下：

 第一步：a.选取{1}    b.在{2,3,4,5}中求解C(4,1);

 第二步：a.选取{2}    b.在{3,4,5}中求解C(3,1);

 第三步：a.选取{3}    b.在{4,5}中求解C(2,1);

 第四步：a.选取{4}     b.在{5}中求解C(1,1);   {4}的序号为3，此时结束
 3、选取三个元素，即求解C(5,3)时，先按序号从数组中顺序取出一个元素，再在取出的元素后面的元素中选取两个元素。设这个序号为i，则当i=5-3=2是时止（i从0开始），因为当i>2时，后面的元素不足2个。
 4、以此类推，即组合C(n,num)的求解过程是：固定位置后，按顺序取出一个元素，再在此元素后面的元素中取num=num-1个元素，当取出的元素个数足够了的时候，即此时num=0时，为递归的出口。

      /*存放输出的数组集合*/
     	private static List<Integer> outArr = new ArrayList<Integer>();
     	/*outArr内存放的数量*/
     	private static int index=0;
     	/**
       *
       * @param inArr 待组合的数组
       * @param n 表示inArr位置，如n=0则从inArr[0]-inArr[length-1]选取数字；n=1，则从inArr[1]-inArr[length-1]选取数字，length为数组长度
       * @param num 要选出数字的数量
       */
     	public static void combNoRep(int[] inArr,int n,int num) {
     		if(num<=0) { //num=0 递归出口
     			for(int i:outArr) {System.out.print(i);}System.out.println();//打印数组
      		}else {
     			for(int i=n;i<=inArr.length-num;i++) {
     				if(outArr.size()<index+1) {outArr.add(index++,inArr[i]);} /*此处两行为防止集合越界空指针异常，如果使用数组存放也可，即此处实现了选取一个元素放进输出数组里，对应上述文字说明2的每一步的a操作*/
     				else outArr.set(index++, inArr[i]);
      				combNoRep(inArr,i+1,num-1); /*在选取的元素后面的元素中选取num-1个元素，对应文字说明2中每一步的b操作*/
      				index--; //重新给输出数组定位，选取一下个序号的元素
      			}
      		}
      	}
      public static void main(String[] arg) {
              int[] arr = {3,2,6,4,5};
              combNoRep(arr,0,3);
          }
  
 

运行结果

文章来源: kangshihang.blog.csdn.net，作者：康世行，版权归原作者所有，如需转载，请联系作者。

原文链接：kangshihang.blog.csdn.net/article/details/117326223