계단 올 라 가기 (심층 검색 + 역 추적) JAVA 해답

N 단계 계단 상승 문제: 한 번 에 2 단계 또는 1 단계 로 갈 수 있 습 니 다. 모든 걷 는 방식 을 인쇄 해 주 십시오.

import java.util.Scanner;
 public class Main{
   private int n;
   private int[] answer;//        
   private int ways;//       
  
   public Main(int n){
      this.n=n;
      answer=new int[n+1];
   }

   public int getWays(){
     return ways;
   }

   // level     step 
   public void  GoUp(int level,int step){
    if(step>n) return;
    if(step == n)//         
    {  
        ways++;  
        for(int i=0; i<level; i++) 
         System.out.printf("%d\t",answer[i]);  
        System.out.println();  
        return;  
    }  
    for(int i=1; i<=2; i++)//2      
    {  
       
     answer[level] = i;//        
     //        ，        level step     ！！   
     GoUp(level+1,step+i);  
     //answer[level]=0;//    ，
      
    }  
   
  }  
  public static void main(String[] args){  
    Scanner in=new Scanner(System.in);
    System.out.println("        ");
    int n =in.nextInt();  
    Main ma=new Main(n);
    ma.GoUp(0,0);  
    System.out.printf("Totally %d ways .
",ma.getWays());  
  }
}  

프로그램 실행:
C:\test>java Main
계단 의 단 계 를 입력 하 세 요
5
1       1       1       1       1
1       1       1       2
1       1       2       1
1       2       1       1
1       2       2
2       1       1       1
2       1       2
2       2       1
Totally 8 ways .
C:\test>java Main
계단 의 단 계 를 입력 하 세 요
6
1       1       1       1       1       1
1       1       1       1       2
1       1       1       2       1
1       1       2       1       1
1       1       2       2
1       2       1       1       1
1       2       1       2
1       2       2       1
2       1       1       1       1
2       1       1       2
2       1       2       1
2       2       1       1
2       2       2
Totally 13 ways .
C:\test>