回溯算法总结

概述

其实回溯算法和我们常说的 DFS 算法非常类似，本质上就是一种暴力穷举算法。回溯算法和 DFS 算法的细微差别是：回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」
抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。
站在回溯树的一个节点上，你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
代码方面，回溯算法的框架：

1. result = []
2. def backtrack(路径, 选择列表):
3.     if 满足结束条件:
4.         result.add(路径)
5.         return
6.    
7.     for 选择 in 选择列表:
8.         做选择
9.         backtrack(路径, 选择列表)
10.         撤销选择

复制代码

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」
回溯算法解决组合问题

这里的组合问题 元素无重不可复选
[code]class Solution {    List res = new LinkedList();    // 记录回溯算法的递归路径    LinkedList track = new LinkedList();    // 主函数    public List combine(int n, int k) {        backtrack(1, n, k);        return res;    }    void backtrack(int start, int n, int k) {        // base case        if (k == track.size()) {            // 遍历到了第 k 层，收集当前节点的值            res.add(new LinkedList(track));            return;        }                // 回溯算法标准框架        for (int i = start; i

东西不错很实用谢谢分享

热心回复！