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

javalearner

接上一篇[学习常用算法之(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]再回溯时，说明已经找完问题的全部解。按上述思想写成程序如下：

1. public class TestComb{
   
2.    public static void main(String args[]){
   
3.       comb(6,3);
   
4.    }
   
5.    public static void comb(int m,int r){
   
6.       int i=0,j;
   
7.       int a[]=new int[100];
   
8.       a[i]=1;
   
9.       do {
   
10.       if (a[i]-i<=m-r+1)/*还能向前试探*/
    
11.       {   if(i==r-1)/*已经找到一个可行的组合解*/
    
12.          {   for (j=0;j< r;j++)
    
13.                System.out.printf("%4d",a[j]);
    
14.             System.out.println();
    
15.          
    
16.          a[i]++;/*调整*/
    
17.          continue;
    
18.          }
    
19.            i++;/*扩展,向前试探*/
    
20.           a[i]=a[i-1]+1;
    
21.       }
    
22.         
    
23.       else/*不能试探,理应回溯*/
    
24.       {   if (i==0) /找到所有可行的解,结束*/
    
25.             return;
    
26.          a[--i]++; /*调整,向后回溯*/
    
27.       }
    
28.    }while(true);
    
29. }
    
30. }
    

复制代码

运行：
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>
  

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/27/000516812.zip