回溯算法尝试

jody970214

在leetcode上面看到跳楼梯的问题，自已想尝试用回溯算法将所有可能的情况全部呈现出来，代码如下（死循环）：

def test():
    
    ans = []
    index = 0

    def go(index, step):
        index += step
        return index
    
    def back(index, step):
        index -= step
        return index
    
    def add_solution(res):
        ans.append(res)
        return ans
    
    def main(list_ = [2,3,1,4], res = []):
        print(index)
        for step in range(1, list_[index] + 1):
            if index < len(list_) - 1:
                res.append(step)
                go(index, step)
                print(index, res)
                test(list_, res)
            elif index == len(list_) - 1:
                add_solution(res)
                back(index, step)
                print(index)
                break
            elif index > len(list_) - 1:
                break
        res = res[:-1]
        print(res, ans)
            
    main()

其中list_的index为楼梯的层数，list_[index]为当前楼梯可行进的最大步数，希望输出ans为所有爬楼的可能走法；
在main中会出现死循环，原因是go和back函数并没有想我想象中的修改index的值，希望大佬能教教我这里是什么原理；
如果能教教我回溯算法就更好了啊哈哈哈

永恒的蓝色梦想

try this:

def test():
    
    ans = []
    index = 0

    def go(index, step):
        nonlocal index
        index += step
    
    def back(index, step):
        nonlocal index
        index -= step
    
    def add_solution(res):
        ans.append(res)
        return ans
    
    def main(list_ = [2,3,1,4], res = []):
        print(index)
        for step in range(1, list_[index] + 1):
            if index < len(list_) - 1:
                res.append(step)
                go(step)
                print(index, res)
                test(list_, res)
            elif index == len(list_) - 1:
                add_solution(res)
                back(step)
                print(index)
                break
            elif index > len(list_) - 1:
                break
        res = res[:-1]
        print(res, ans)
            
    main()

这个是变量作用域和不可变对象的问题。

PS：建议楼主先打好基础，再去力扣做题哦