JSで登山階段の練習をバックトラックする方法を教えてもらえますか？

Question

関数内でバックトラックを実装する際に問題が発生しています。ちょっとしたプッシュが必要なような気がします。私はあなたがリンクされるコードの戦いから取られた質問を持っていますhere

あなたはn個の階段を持つ階段を登る必要があり、階段を上げることによって余分な運動をすることに決めました。 1回のジャンプで最大kステップまでカバーすることができます。ソートされた階段を登るために取ることができるすべてのジャンプのシーケンスを返します。私はバックトラックの考え方でこの問題に来ることになっています

climbingStaircase(n, k) = [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]] 

が、バックトラックは私に新しいですし、私は、ハードを持っています：N = 4、K = 2の場合

、出力は次のようになりますそれを関数で実装する時間。私は危機に瀕しているように感じるが、ちょっとしたプッシュが必要だ。私はこれを解決し、バックトラッキングを完全に理解するのを助けることができる人がいますか？

Answer 1

私は同じ問題で立ち往生しましたが、私はそれを解決しました。ここにJavaのソリューションです：

ArrayList<int[]> solutions = new ArrayList<int[]>(); 

    int[][] climbingStaircase(int n, int k) { 
     climb(new int[n*k], 0, 0, 0, n, k); 
     return trimSolution(solutions); 
    } 

    void climb(int[] sol, int index, int step, int sum, int max, int stepMax) { 
     if(step != 0) { 
      sum += step; 
      sol[index++] = step; 
      if(sum < max) { 
       // printArray("it: ", sol); 
      } else if(sum == max){ 
       // printArray("sol: ", sol); 
       solutions.add(trimSolution(sol)); 
       sol[--index] = 0; 
       return; 
      } else { 
       sol[--index] = 0; 
       // printArray("failed: ", sol); 
       return; 
      } 
     } 

     for (step = 1; step <= stepMax; step++) { 
      // System.out.println("index: " + index); 
      climb(sol, index, step, sum, max, stepMax); 
     } 
    } 

    int[] trimSolution(int[] sol) { 
     int length = 0; 
     for (int i = 0; i < sol.length; i++) { 
      if(sol[i] != 0) 
       length++; 
     } 
     int[] r = new int[length]; 
     for (int i = 0; i < r.length; i++) { 
      r[i] = sol[i]; 
     } 
     return r; 
    } 

    int[][] trimSolution(ArrayList<int[]> sol) { 
     if(sol.size() == 0) 
      sol.add(new int[0]); 
     int[][] r = new int[sol.size()][1]; 
     for (int i = 0; i < sol.size(); i++) { 
      r[i] = sol.get(i); 
     } 
     return r; 
    } 

void printArray(String message, int[] a) { 
    System.out.print(message); 
    for (int i = 0; i < a.length; i++) { 
     System.out.print(a[i] + ", "); 
    } 
    System.out.println(); 
}