Quelqu'un peut-il m'aider à mettre en place un retour en arrière pour une escalade dans JS?

Question

J'ai du mal à faire marche arrière dans une fonction et j'ai l'impression d'avoir besoin d'un peu de pression. J'ai une question tirée de combats de code que je vais lier here

Vous avez besoin de monter un escalier qui a n étapes, et vous décidez de faire un peu d'exercice en sautant les étapes. Vous pouvez couvrir au maximum k étapes dans un seul saut. Retourne toutes les séquences possibles de sauts que tu pourrais prendre pour monter l'escalier, triés.

Pour n = 4 et k = 2, la sortie doit être:

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

Je suis censé venir à ce problème avec un état d'esprit de retour en arrière, mais retours en arrière est nouveau pour moi et je suis d'avoir un disque le temps de l'implémenter dans une fonction. Je me sens comme si je suis sur le point, mais j'ai juste besoin d'un petit coup de pouce. Y a-t-il quelqu'un là-bas qui peut m'aider à résoudre cela et à comprendre complètement le retour en arrière?

Answer 1

J'étais coincé dans le même problème, mais je l'ai résolu. voici la solution en 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(); 
}