单次跳跃最多回溯 n 个楼梯，最多 k 步

您需要爬一个有 n 个台阶的楼梯，并且您决定通过跳上台阶来获得一些额外的锻炼。单次跳跃最多可以完成 k 步。返回爬楼梯时所有可能的跳跃顺序，并排序。

我的实施显然给了我错误的答案。

def climbingStaircase(n, k):
    final_res=[]
    final_res.append(CSR(n,k,[]))
    return final_res

def CSR(n,k,res):
    if n == 0:
        return res        
    else:
        for i in range(1,k+1):
            if n-i>=0:
                res.append(i)
                n=n-i
                res=CSR(n,i,res)
        return res

对于 n = 4 且 k = 2，输出应为

[[1, 1, 1, 1],
 [1, 1, 2],
 [1, 2, 1],
 [2, 1, 1],
 [2, 2]]

实际输出：

[[1,1,1,1,2,1]]

有人能指出我缺少哪一部分吗？

下面的代码中存在一个巨大的问题：您扣除了以下步骤的数量：each步长范围内的可能性。

n=n-i
res=CSR(n,i,res)

当您探索完一步跳跃可以做什么后，您需要回溯并尝试从same起点（该实例的原始值n) 进行 2 步跳跃。将代码更改为：

res = CSR(n-i, i, res)

这保持了n当你经历循环时，值保持不变。

此外，您不能将未来的跳跃限制为您刚刚获得的最大值。也更改第二个参数：

res = CSR(n-i, k, res)

这应该会让你动起来。也试试这个可爱的debug博客寻求帮助。至少插入一两个跟踪语句，例如

print n, k, res

在你的日常工作的顶部。

CAVEAT

这还不是你的全部麻烦。剩下的最大问题是CSR仅返回一个解决方案：您采取的每一步都会附加到same列表。您需要一种方法将已完成的解决方案收集为单独的列表；这append in climbingStaircase仅执行一次，之后CSR已经完全完成了。

您需要在以下位置认可完整的解决方案n==0.

调试帮助

这是程序的一个版本，固定了递归参数，并插入了调试跟踪。

indent = ""

def climbingStaircase(n, k):
    final_res = []
    final_res.append(CSR(n, k, []))
    return final_res

def CSR(n, k, res):
    global indent
    indent += "  "
    print indent, n, k, res
    if n == 0:
        print "SOLUTION", res
    else:
        for i in range(1, k+1):
            if n-i >= 0:
                CSR(n-i, k, res + [i])
    indent = indent[:-2]

print climbingStaircase(4, 2)

请注意使用“缩进”来帮助可视化您的递归和回溯。这里的关键部分是，而不是更新res在全局范围内，我将其保留为局部变量。我也曾removed现在的返回值，只需转储即可输出找到的解决方案。您可以看到它是如何工作的：

   4 2 []
     3 2 [1]
       2 2 [1, 1]
         1 2 [1, 1, 1]
           0 2 [1, 1, 1, 1]
SOLUTION [1, 1, 1, 1]
         0 2 [1, 1, 2]
SOLUTION [1, 1, 2]
       1 2 [1, 2]
         0 2 [1, 2, 1]
SOLUTION [1, 2, 1]
     2 2 [2]
       1 2 [2, 1]
         0 2 [2, 1, 1]
SOLUTION [2, 1, 1]
       0 2 [2, 2]
SOLUTION [2, 2]
[None]

有了这些东西，我希望您能够跟踪您的逻辑并找出如何在您选择的级别捕获解决方案的顺序。