Go语言视频零基础入门到精通

thinkinjava

接上一篇[学习常用算法之(3)回溯法]
【问题】 组合问题
问题描述：找出从自然数1，2，…，n中任取r个数的所有组合。
采用回溯法找问题的解，将找到的组合以从小到大顺序存于a[0]，a[1]，…，a[r-1]中，组合的元素满足以下性质：
（1） a[i+1]>a，后一个数字比前一个大；
（2） a-i<=n-r+1。

按回溯法的思想，找解过程可以叙述如下：
   首先放弃组合数个数为r的条件，候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1），候选组合改为1，2。继续这一过程，得到候选组合1，2，3。该候选解满足包括问题规模在内的全部条件，因而是一个解。在该解的基础上，选下一个候选解，因a[2]上的3调整为4，以及以后调整为5都满足问题的全部要求，得到解1，2，4和1，2，5。由于对5不能再作调整，就要从a[2]回溯到a[1]，这时，a[1]=2，可以调整为3，并向前试探，得到解1，3，4。重复上述向前试探和向后回溯，直至要从a[0]再回溯时，说明已经找完问题的全部解。按上述思想写成程序如下：


public class TestComb{
   public static void main(String args[]){
      comb(6,3);
   }
   public static void comb(int m,int r){
      int i=0,j;
      int a[]=new int[100];
      a=1;
      do {
      if (a-i<=m-r+1)/*还能向前试探*/
      {   if(i==r-1)/*已经找到一个可行的组合解*/
         {   for (j=0;j< r;j++)
               System.out.printf("%4d",a[j]);
            System.out.println();
         
         a++;/*调整*/
         continue;
         }
           i++;/*扩展,向前试探*/
          a=a[i-1]+1;
      }
        
      else/*不能试探,理应回溯*/
      {   if (i==0) /找到所有可行的解,结束*/
            return;
         a[--i]++; /*调整,向后回溯*/
      }
   }while(true);
}
}

运行：
C:\java>java TestComb
1 2 3
1 2 4
1 2 5
1 2 6
1 3 4
1 3 5
1 3 6
1 4 5
1 4 6
1 5 6
2 3 4
2 3 5
2 3 6
2 4 5
2 4 6
2 5 6
3 4 5
3 4 6
3 5 6
4 5 6

C:\java>