回溯算法（第一章 基础）

这一章我们只讲思想，不做复杂题。

1. 前提条件

回溯（Backtracking）不是一种数据结构。

也不是一种具体算法。

它是一种：算法设计思想

主要解决：

枚举所有方案

搜索所有可能

找满足条件的方案

 剪枝优化

典型题：

子集

组合

排列

N皇后

数独

组合总和

2. 回溯到底是什么？

试一条路

↓
如果不行

↓

退回来
↓

换另一条路

所以：Backtracking

↓

回退

↓

回溯

例如：

走迷宫：

        A

      /   \

     B     C

    /

   D

走：

A

↓

B

↓

D

发现：

死路

于是：

退回B

↓

退回A

↓

走C

这就是：

回溯。

3. 回溯和DFS区别

DFS

是一种遍历方式。

例如：

树：

0

↓

1

↓

2

DFS：访问所有节点。

而回溯：

不是为了遍历。

而是枚举所有可能。

例如：
123

所有排列

DFS：

只是访问：

1

2

3

回溯：

123

132

213

231

312

321

完全不是一个目标。

4. 回溯为什么是DFS升级？

因为它也是：

一路走到底。

例如：

组合：

1

↓

2

↓

3

但是：

DFS到底结束。

直接：return

然而回溯：

到底以后

还要撤销刚刚的选择。

例如：

path

↓

[1]

↓

[1,2]

↓

[1,2,3]

结束。

不是直接结束。

而是：

删除3

↓

删除2

↓

继续尝试其它数字

所以：

回溯：

比DFS：

多了一步恢复现场。

5. 回溯的四步

① 做选择

↓

② 递归

↓

③ 撤销选择

↓

④ 换另一种选择
也即是：
选择

↓

递归

↓

恢复

↓

继续

6. 回溯为什么必须恢复？

举个例子。

例如：

求：

123

所有排列

开始：

path

[]


选择：

1

path：

[1]

继续：

选择：

2

path：

[1,2]

继续：

3

得到：

[1,2,3]

记录答案。结束。

现在如果不恢复path：

还是[1,2,3]

那么以后根本没法尝试：

1

3

2

所以必须删掉3

变[1,2]

继续。

7. 回溯固定模板

void dfs(...)
{
    if(结束条件)
    {
        保存答案;
        return;
    }

    for(...)
    {
        做选择;

        dfs(...);

        撤销选择;
    }
}


8. 一个例子

例如：

从：

1

2

3

任选。

代码：

void dfs()
{
    for(int i=1;i<=3;i++)
    {
        printf("%d ",i);
    }
}

这不是回溯。

因为没有恢复。

真正回溯：

path.push(i);

dfs();

path.pop();

这里：

push

↓

递归

↓

pop

就是回溯。

9. 回溯代码模板
void dfs(...)
{
    if(满足条件)
    {
        保存答案;
        return;
    }

    for(...)
    {
        //① 做选择
        path[pathSize++] = 当前元素;

        //② 递归
        dfs(...);

        //③ 撤销选择
        pathSize--;
    }
}

pathSize--

不是删除数组。

而是逻辑删除。

以后都会这样写

10. 回溯为什么不用真的删除？

例如数组：

path

↓

1

2

3

现在：

pathSize=3;

删除：

3

其实代码只有：

pathSize--;

变成：

pathSize=2

数组实际上还是：

1

2

3

只是以后只看前2个。

所以效率：非常高。

11. 回溯总结
Backtracking

核心思想：

    做选择

↓

    递归搜索

↓

    撤销选择

↓

    尝试下一种可能

与DFS区别：

DFS：

    遍历

Backtracking：

    搜索所有方案

固定模板：

for

↓

选择

↓

递归

↓

恢复

↓

继续