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]

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

[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的副本

[sunshinesDL]

补充：这里应该添加 path 列表的浅拷贝，而非此列表的引用。
为什么不直接插入引用？ 因为列表是可变类型，而 path 列表随着最后一个节点弹出，最后会变为空。所以若直接向 res 插入 path 的引用，随着 path 变为空列表，res 中已经插入的 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!

[LeoooKang]

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

[krahets]

谢谢指正！

[480284856]

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

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

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

[Odysseus527]

正好对应了封面图

[xici]

框架代码中的这个部分

/* 回溯算法：例题三 */
void backtrack(TreeNode *choices[2]) {
    //code...
}

其中(TreeNode *choices[2])里面的choices[2]，请问这里的2指的是choices这个序列中共有两个选择，还是指choices这个序列中下标为2的项？thanks🙏

[JackTvT]

左右子树，所以是两个选择

[xici]

ok谢谢

[syutengu]

原文列举了汉诺塔作为回溯经典例题，想请教这就是个单纯的递归问题，怎么去用回溯法呢？一直没想出来。

[wind-FL]

个人想法是采用穷举法求解汉诺塔问题，因此采用回溯

[zhuyihuan68]

不用想 相比递归太复杂了
using System;
using System.Collections.Generic;

public class HanoiBacktracking
{
// 三根柱子
private Stack[] towers;
private int n; // 圆盘数量
private List moves; // 记录移动步骤
private bool foundSolution;

public List<string> Solve(int n)
{
    this.n = n;
    towers = new Stack<int>[3];
    for (int i = 0; i < 3; i++)
        towers[i] = new Stack<int>();
    
    // 初始化：将所有圆盘按从小到大放入塔0
    for (int i = n; i >= 1; i--)
        towers[0].Push(i);
    
    moves = new List<string>();
    foundSolution = false;
    
    // 开始回溯
    Backtrack();
    return moves;
}

private void Backtrack()
{
    // 检查是否达到目标状态
    if (IsSolution())
    {
        foundSolution = true;
        return;
    }

    // 尝试所有可能的移动：从柱子from到柱子to
    for (int from = 0; from < 3; from++)
    {
        for (int to = 0; to < 3; to++)
        {
            if (from == to) continue; // 不能移动到同一根柱子

            if (IsValidMove(from, to))
            {
                // 做出选择：移动圆盘
                int disk = towers[from].Pop();
                towers[to].Push(disk);
                moves.Add($"Move disk {disk} from tower {from} to tower {to}");

                // 递归探索
                Backtrack();
                if (foundSolution) return; // 找到解后直接返回

                // 撤销选择：回溯
                towers[to].Pop();
                towers[from].Push(disk);
                moves.RemoveAt(moves.Count - 1);
            }
        }
    }
}

private bool IsValidMove(int from, int to)
{
    // 源柱子不能为空
    if (towers[from].Count == 0)
        return false;
    
    // 目标柱子为空或顶部圆盘大于要移动的圆盘
    if (towers[to].Count == 0)
        return true;
    
    return towers[from].Peek() < towers[to].Peek();
}

private bool IsSolution()
{
    // 检查塔2是否有n个圆盘，且按从小到大排列
    if (towers[2].Count != n)
        return false;
    
    int[] disks = towers[2].ToArray();
    for (int i = 0; i < n; i++)
    {
        if (disks[i] != i + 1)
            return false;
    }
    return true;
}

}

[Huah-Yin]

first day

$day_1 wriiten by Haihua$

[zdjray]

模板方法提炼的不错，可以变成类库了

[xiaos2021]

学习了本篇框架代码，我和前面某个读者留言有类似的思考和建议。1，抽象的框架代码中，在触发深层递归之前，可以考虑增加一个函数 generateNextChoices() ，用于生成用于给下一步递归使用的参数。2，抽象的框架代码中，增加更多的注释，更利于新手理解如何使用该框架。3，抽象的框架代码中，最后增加一个return语句，用于显式地表示本层递归的结束，即将返回到上一层。
我写了 C++ 代码如下。

/* 回溯的框架代码 */
void backtrack(StateType& state, vector<ChoiceType>& choices, vector<StateType>& result) {
    // 检查：当前状态是否为解
    if (isSolution(state)) {
        // 检查成功，记录解
        recordSolution(state, result);
        // 在记录完成当前解后，根据题目需要，选择是否要提前结束。如果需要结束递归，则使用return
        // 注意，某些题目不需要提前结束，则删除return语句
        return;
    }
    // 穷举：遍历当前层的所有选择
    for (ChoiceType choice : choices) {
        // 剪枝：提前判断，即将做出的该选择是否符合约束条件，如果符合那么继续，否则直接跳过
        if (isValid(state, choice)) {
            // 尝试前进：做出该选择，更新状态
            makeChoice(state, choice);
            // 触发递归：基于当前选择，生成下一步的深层选择，然后继续向深层走，触发递归
            // 注意，某些题目不需要生成下一步选择，则删除generate函数，直接使用choices作为参数
            vector<ChoiceType> nextChoices = generateNextChoices(choice, choices);
            backtrack(state, nextChoices, result);
            // 回退：撤销该选择，恢复到 做出该选择 之前的状态
            undoChoice(state, choice);
        }
    }
    // 返回：退出本层递归
    return;
}

相应的例题三的框架代码中，提取出一个单独的 generateNextChoices() 函数。

/* 基于当前选择，生成下一步的深层选择 */
vector<TreeNode*> generateNextChoices(TreeNode* choice) {
    vector<TreeNode*> nextChoices({choice->left, choice->right});
    return nextChoices;
}

[Chad-Wu]

模板代码思路很清晰，hhhh用这个一晚上刷了5道hot100上的回溯题