写于N-Queen后 回溯小结

回溯算法，关键就在题面上，我们是反向来捋逻辑的，而不是正向

最先考虑递归的结束条件，即得到什么结果时，会将path加入结果集

简单的形容，回溯算法就是特殊情况下的深度优先算法

大多使用深度优先算法时是遍历找到某个节点

回溯作为其中的小部分，它的目标是找到一条达成目标的路径

可以看做同样是对一个满N叉树进行深度优先遍历

枝干节点代表每一步做出的选择

叶子节点代表依此路径选择的最终情形

从根节点到叶子节点的所有情况都会遍历到

无论满不满足，能不能加入结果集，都会return

只是只有满足要求条件的会加入结果集而已

一般的回溯函数形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func backtrack(args...){
    if(flag){
        result = append(result, path...)
    }else {
        // 一般，我们会在此时，对输入的参数进行一定的判断和调整
        doSomeThing()
        
        // 递归调用下一层
        backtrack()
        
        // 从下一层回来后，不论下一层做了什么，恢复本层的更改
        undoSomething()
    }
    
    // OR
    for(flag2){
        doSomeThing()
        backtrack()
        undoSomething()
    }
    
    // -------------------------------------
    // -------------------------------------
    // --------------逻辑代码结束-------------
    // -------------------------------------
    // -------------------------------------
}

我们并不需要关注flag不满足时，递归会递归到何处

因为flag不满足时，递归到最后函数仍然会返回

如题中，逻辑代码结束处，就是不满足条件，无法加入结果集的递归路径的终点

再从终点一步步向上回溯

  • 终点为空，未做任何改变，结果集自然也不会受任何影响，继续回溯
  • 终点达成条件，添加进结果集，继续回溯

即，不论添加入结果集的条件如何，添不添加其余操作，一般都不影响需要遍历的数量

最多提前限定一定条件进行剪枝，专门来减少需要遍历的数量