问答详情
源自:-

回溯法中的恢复现场,是在递归的每一步都恢复,还是在递归完成后恢复

结合代码理解的过程发现,有恢复现场的代码存在,是如何把结果打印下来的

if depth == len(data_list)+1:

        print(arranges)

        global total

        total += 1

    else:

        for data in datas:

            #1. 设置现场

            arranges.append(data)

            #2. 递归

            next_datas = datas[:]

            next_datas.remove(data)

            search(depth+1, next_datas)

            #3. 恢复现场

            arranges.pop()

这里恢复现场不是把arranges.pop掉了,这样递归完成后arranges应该是空列表了把,   为什么print(arranges)的时候还能打印出来呢


提问者:hzyhan 2020-01-22 23:17

个回答

  • weixin_慕移动8336811
    2020-03-04 07:31:21

    注意arranges.pop()或者说pop()这个函数只会弹出数组的最后一个元素,也就是说会去掉你选的(递归开始的地方)上一个元素。所以递归完成后不一定是空列表。比如[1,2,3]  #1设置现场 arrange = [1,2] #2.递归 next_datas = [3], 这一步也就只有一个元素可选,直接一种可能[1,2,3] ,#3 恢复现场 arrange = [1],继续设置下一个现场为[1,3]....