                        课程
                    
                        /计算机基础
                        
                            /算法与数据结构
                        
                        /Python 算法面试难点攻坚课--动态规划

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

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

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

源自：Python 算法面试难点攻坚课--动态规划

关注问题我要回答

1440

操作

收起

1 回答

weixin_慕移动8336811
2020-03-04

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