回溯算法

回溯算法的应用有两个关键点：

1 要选择好剪枝条件，即什么时候进行回溯.

2 要控制好传递的参数，回溯函数每次返回来的时候，仍然是原来的值，不要随机更改值，常用的技巧是在函数传参的时候顺便修改参数的值，此外如果要增加限制条件的时候，可以在回溯函数中增加参数.回溯函数每次回溯结束的时候就会把以前的内存释放掉

一 回溯算法模板

回溯算法要注意三个要点

a. 利用深度优先遍历时的结束条件,如果满足结束条件了,则将生成好的数据存储,结束本次回溯,否则继续回溯

b. 状态恢复,即每次调用回溯函数backtrack()结束的时候,要返回调用前的状态.

c. 合理的剪枝条件,画树状图的时候就判断出哪些分支不需要,及增加什么条件即可以把该枝去掉.

技巧:

1 对于有的回溯算法如力扣60题第K个排列,回溯的过程中一旦满足条件就需要停止,这时候就要把回溯函数写到return后面,最下层的回溯函数中的if len(a) == n: return a条件一旦满足了,回溯函数就会逐层将a返回.否则的话由于每次函数调用的时候都会压栈出栈,出栈的时候会恢复以前的状态,这时候需要定义全局变量来记录回溯函数调用的次数,非常繁琐,而用return的话很简洁.

2 对于有些for循环的剪枝情况,要会用continue来结束一次for循环,不要只会用break,直接把整个for循环都结束了.

3 想要选好的剪枝条件,必须要先选几个典型的数据,亲自动手画出树状图,通过树状图来观察出哪些枝需要剪掉,再归纳出对应的剪枝条件,把条件加入程序中.

4 对于可变对象,压栈完成后一定要记得出栈,比如a.append(k) a.pop(),否则很容易出错,特别是在同级的for循环中,

对于可变对象,如果是回溯函数直接传参的时候修改的,且变量名相同(局部变量和全局变量),则回溯函数结束调用后会自动恢复之前的值.

def fun1(x):
    x.append([6,7])
    x[0] = 999
    y[0] = 999
    return
def fun2(x1):
    x.append([6,7])
    x[0] = 999
    x1.append([6,7])
    x1[0] = 999
    return
y = [5,5,5]
x = [1,2,3]
# 这里x y都是可变对象,但是y的值被修改了但x的值却没有变,原因是fun1中的局部变量的名字是x,
# 恰恰和全局变量相同了,这时候fun1中的x都认为是局部变量了,所以修改x中的值后,函数结束调用后就会释放掉内存,所以x的值不会被修改
# 而同样的全局变量y便被修改了
fun1(x+[4,5])
print('x的值没有变:',x)
print('y的值变了:', y)
# 这次全局变量x的值被修改了,可见如果在回溯函数中用fun1中的方法,则每次调用结束后,会自动恢复前面的值,
fun2(x+[8,9])
print('x的值变了', x)
# x的值没有变: [1, 2, 3]
# y的值变了: [999, 5, 5]
# x的值变了 [999, 2, 3, [6, 7]]