回溯算法

文章 97 字

遇到计算排列或者组合的问题,总是可以通过回溯的思想来解决。回溯的处理思路,就是遇到了岔路口,按照顺序依次去走每一个小路,当前的小路走不通时, 重新回到上一个岔路口,记录走另一条没有走的路。

可能会有多个岔路,从数据结构的角度去分析,就是一个多叉树。而不停的回溯过程,就等价于多叉树的编历操作。二叉树的编历都是使用递归来实现,回溯算法 一般使用的是中序编历:左节点-根节点-右节点

回溯算法

回溯算法的有写比较重要的点,我们依次来说明

构造一个树的结构

将问题抽象成一个树的遍历结构是根本

递归的退出条件

递归的退出条件,递归的退出条件肯定要在递归函数被调用之前判断,如果放到了递归函数调用之后,那绝对会导致栈溢出。这个退出的条件多种多样,我们可以 通过控制递归的深度来确定是否要退出、或者遇到某个重复值执行退出。

递归中状态的更新和回退

在回溯的过程中,无可避免的会涉及到状态的回退。如果我们使用固定的空间来保存从根节点到叶子节点的一条路径,我们首先遍历做子树,当左子树遍历完成之 后,我们开始遍历右子树之前,需要清空固定空间中的左子树节点。

有时候还要配合上去重过滤,也是状态的更新和回退。下面突出的两行就是状态的更新和回退

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 回溯所有遇到的情况
func find(candidates []int, target int, start int, temp []int) {

    for i := start; i < len(candidates); i++ {
        
        less := target - candidates[i]
        if less < 0 {
            continue
        }

        temp = append(temp, candidates[i])
        if less == 0 {
            gloablResult = append(gloablResult, append([]int{}, temp...))
        } else {
            find(candidates, target - candidates[i], i, temp)
        }
        
        temp = temp[:len(temp)-1]
    }
}