chapter_backtracking/backtracking_algorithm/

[giscus[bot]]

chapter_backtracking/backtracking_algorithm/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_backtracking/backtracking_algorithm/

[jienian]

不错，很好理解！

[Poss-xiaohu]

通俗易懂！

[heyJayhey]

非常好！很细节很通俗，支持支持！

[suson-struggle]

k神，你好，如果为 4 节点新增一个 left 节点，值也为7，那么回溯算法无法搜索到 [1, 7, 4, 7] 的路径，但是把记录解后面的 return 语句去除就能搜索到，请问这个 return 语句的作用是什么呢？

[krahets]

Hi 很细心啊，确实。一般情况下，找到解以后无需继续搜索，因此在 record_solution() 之后通常会加 return 。例如后面介绍的全排列、子集和、N 皇后都具有这样的特性。

文中的例题由于没有给出任何其他约束，因此除了在遇到 3 时应该剪枝外，其余情况都不能剪枝，包括 record_solution() 之后，因此不应该加 rerturn 。

[jiangyigithub]

/* 前序遍历：例题三 */
void preOrder(TreeNode *root) {
    // 剪枝
    if (root == nullptr || root->val == 3) {
        return;
    }
    // 尝试
    path.push_back(root);
    if (root->val == 7) {
        // 记录解
        res.push_back(path);
        return;
    }
    preOrder(root->left);
    preOrder(root->right);
    // 回退
    path.pop_back();
}


in the code block
{
    if (root->val == 7) {
        // 记录解
        res.push_back(path);
        return;
    }
}

it seem have some issue if use "return" here.

i use the test code.

//       5
//      /  \
//     4    8
//    /      / \
//   11  13  14
//  /  \          / \
// 7    2     5   7

int main()
{
    string line = "[5,4,8,11,null,13,14,7,2,null,null,5,7]";

    TreeNode *root = stringToTreeNode(line);

    Solution* slt = new Solution();
     slt->preOrder(root);
    vector<vector<int>> output = slt->res;
}

the result: 5->4->11->7 5->4->8->14->7

[krahets]

Solution 1: Record path and return when finding a node of value 7. Before returning, we should REDO the state.

Solution 2: Only record path when finding 7, and continue searching.

[jiangyigithub]

the output of the two solutions for the test case [5,4,8,11,null,13,14,7,2,null,null,5,7] are same.

[jiangyigithub]

how to understand, do these two solutions is unified?

[jiangyigithub]

maybe you can reply me in Chinese, i use English owing to the input method of my linux PC issue. Thanks.

[krahets]

Please try the test case [5,4,8,11,null,13,14,7,2,null,null,5,7,null,null,7] and compare them.

# Solution 1
[5, 4, 11, 7]
[5, 8, 13, 7]

# Solution 2
[5, 4, 11, 7]
[5, 4, 11, 7, 7]
[5, 8, 13, 7]

We get [5, 4, 11, 7, 7] in Solution 2 because it will continue searching when finding node 7.

[zhuasdfg]

通俗易懂，例子也举的好，框架实际应用前序遍历的例子太妙了，就喜欢看这种有实际实现例子的方法论

[Allen-Ciel]

怎么理解回溯和递归的关系？

[krahets]

好问题！总的来看，回溯是一种“算法策略”，而递归更像是一个“工具”。

• 回溯算法通常基于递归实现。然而，回溯是递归的应用场景之一，是递归在搜索问题中的应用。
• 递归的结构体现了“子问题分解”的解题范式，常用于解决分治、回溯、动态规划（记忆化递归）等问题。

[likz1994]

大神真的努力教会 麻瓜使用魔法。

[krahets]

改名霍格沃茨魔法学校？

[Zhuzhucatty]

我支持！

[5710xIa]

python里，恢复状态undo_choice(state: list[TreeNode], choice: TreeNode)不需要用到choice: TreeNode

[krahets]

这个要看具体题目哈

[muzishuiji]

k神，有一个问题想请教下。

   // 遍历所有选择
    for (let choice of choices) {
        
    }

回溯框架里的choices，针对树结构的choices怎么处理呀？等价于树结构前序遍历生成的数组吗？

[krahets]

在树的回溯问题中，通常选择为当前节点的各个子节点。choices 为树的情况可能比较少，方便举个例子吗？

[chen-xiao-yu]

一开始应该就是根节点

[Anewman211]

第一次调用backtrack应该这样传参backtrack（[root],[root.left, root.right],[]）吗？

[krahets]

@Anewman211 Hi，应该是 backtrack(state=[], choices=[root], res=res) 。建议去代码仓库下载完整代码，可以一键运行的。

[Curyain]

恐怖如斯

[chen-xiao-yu]

上学的时候就从这里开始就搞不动了，现在好像还是差不多， 前面那一堆都花个两三天时间就搞定

[krahets]

加油鸭

[MidPG]

生动形象！

[sparkTesal]

for choice in choices:
        # 剪枝：判断选择是否合法
        if is_valid(state, choice):
            # 尝试：做出选择，更新状态
            make_choice(state, choice)
            backtrack(state, choices, res)
            # 回退：撤销选择，恢复到之前的状态
            undo_choice(state, choice)

backtrack(state, choices, res)
模板中这行代码是有些问题的吧，进行递归的时候choices应该已经变化了，但是还是和make_choice之前的choices是一个列表。
从下面的例子也能看出来，用的是Arrays.asList(choice.left, choice.right)，而不是直接用的choices

[krahets]

Hi，这个取决于具体问题的性质，很多问题的 choices 是不变的，例如下一节的“全排列问题”，choices 始终是所有候选元素

[wcig]

博主，例题二、三的 go 代码中，将 path 添加到 res 这一行代码需要调整下，因为 go 的切片是一个指针指向底层数组，可能会造成数据错误。博主可以在样例树为值为 6 的节点添加一个值为 7 的左儿子节点测试看看。

/* 前序遍历：例题二 */
func preOrderII(root *TreeNode, res *[][]*TreeNode, path *[]*TreeNode) {
    if root == nil {
        return
    }
    // 尝试
    *path = append(*path, root)
    if root.Val.(int) == 7 {
        // 记录解
        // 修改前
        // *res = append(*res, *path)
        // 修改后
        *res = append(*res, append([]*TreeNode{}, *path...))
    }
    preOrderII(root.Left, res, path)
    preOrderII(root.Right, res, path)
    // 回退
    *path = (*path)[:len(*path)-1]
}

[Reanon]

是的，这里需要修改一下

[Terran0629]

作者你好，我有点不理解，对例题三进行框架代码的运行时，backtrack第一次运行的时候choices是[1]，那为什么可视化运行那里choices指向的是[0]这个列表啊，不应该是[1]吗

[Terran0629]

骚瑞，根节点有指向那个列表，没看见

[Yerosius]

如果对回溯难以理解，说明递归没有真正完全掌握，建议先复习高中的数学归纳法，并善用VS、CLion等IDE的并行堆栈、并行监视功能，他们都是帮助理解递归和回溯的优秀工具。

[00booker]

回溯典型例题，哪里可以刷这些例题嘛，回溯算法还是比较薄弱

[krahets]

推荐 https://github.com/krahets/LeetCode-Book ，题单中有回溯例题

[sun-unc]

树的回溯算法我能理解 但是数组的回溯该怎么理解

[krahets]

一样的，虽然是数组，但回溯的过程也会形成一个“递归树”。可以看下一节“全排列”加深理解

[xxc111111]

我觉得树可视化还是有点问题，比如当左子树构建完成后会立即构建右子树，而不是先返回根节点

[lixianglong1205]

献丑下二叉树的前序遍历算法:

def pre_order(root: TreeNode):
    return [] if not root else [root.val] + pre_order(root.left) + pre_order(root.right)

[Steve-Ljs]

在剪枝中

res.append(list(path))

这句话一定要加上list，不加上list的话，这个path只是一个引用，最后是不会输出的，只有list(path)才是将其转为path的副本

[chaojiwudidashuaige492]

请问makeChoice()改成completeChoice()会不会更好一点

[lieren1922]

rust版本回溯框架代码解决问题3，对None进行unwrap会panic。用if let或者match解包：

// 安全地处理 left 和 right 子节点
let mut next_choices = Vec::new();
if let Some(left) = choice.borrow().left.clone() {
    next_choices.push(left);
}
if let Some(right) = choice.borrow().right.clone() {
    next_choices.push(right);
}

// 进行下一轮选择
backtrack(state, &mut next_choices, res);

[krahets]

@rongyi Please help check this comment at your convenience, thanks!

[WalkerInAI]

• 图 13-2 尝试与回退
  中 <11>
  的 列表 res
  最右侧多了一个 ' ] '

[krahets]

谢谢指正！

[480284856]

回溯算法就像是走迷宫，我们需要在迷宫中记录所有从迷宫入口到有金币的小道的路径时的路径规划方法一样：
在迷宫入口，
首先看看脚底下有没有金币，有的话，我就把路线记录下来（is_solution），
然后我们会有若干个路口可以选择（choices），
接着我们要一个个判断路口是否可以通过（is_valid），

1. 如果可以，我们就尝试走这个路口（make_choice），
   a. 使用影分身之术，告诉分身当前你在个小道里（state，注意此时分身走进路口），分身所在 的小道有几个岔路口（choices）以及如果找到了有金币的路径的话，应该汇总到哪里（res）
   b. 等待分身结束探索后，让分身获得的经验融入到本体中。
2. 如果不可以，那么就尝试其他路口。

在尝试了所有的路口后，所有可能已尝试完毕。

[Odysseus527]

正好对应了封面图