如何在 JS 中实现爬楼梯练习的回溯?

Question

我在函数中实现回溯时遇到问题。我有一个从代码战斗中获取的问题，我将在此处链接。

你需要爬一个有n个台阶的楼梯，你决定通过跳上台阶来做一些额外的锻炼。您最多可以在一次跳跃中覆盖 k 步。返回所有可能的跳跃序列，您可以采取

这些跳跃来爬楼梯，排序。对于 n = 4 和 k = 2，输出应为：

climbingStaircase(n, k) = [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 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();
}