【算法】递归型枚举与回溯剪枝初识

1. 什么是搜索？搜索，是一种枚举，通过穷举所有的情况来找到最优解，或者统计合法解的个数。因此，搜索有时候也叫作暴搜。搜索一般分为深度优先搜索(DFS)与宽度优先搜索(BFS)。
2. 深度优先遍历 vs 深度优先搜索，宽度优先遍历 vs 宽度优先搜索。遍历是形式，搜索是目的。不过，在一般情况下，我们不会去纠结概念的差异，两者可以等同。
3. 回溯与剪枝

• 回溯：当在搜索的过程中，遇到走不通或者走到底的情况时，就回头。
• 剪枝：在搜索过程中，剪掉重复出现或者不是最优解的分。

递归型枚举与回溯剪枝初识：

• 画决策树。
• 根据决策树写递归。

搜索的本质：对决策树进行一次遍历，直到将所有的情况搜集到为止。

1.枚举子集

B3622 枚举子集（递归实现指数型枚举）

解法：深搜

设一共有 3 人，分别是 1，2，3。「从前往后」考虑每一个人，针对当前这个人「选」或者「不选」，我们可以画出如下「决策树」：

设计递归函数：

1. 重复子问题：针对某一位，「选」或者「不选」。因为最终结果要按照「字典序」输出，我们可以「先考虑不选」，然后「再考虑选」。
2. 实现方式参考代码和注释，结合「决策树」一起看会很清晰。

#include<iostream>
#include<string>
using namespace std;

const int N = 11;

int n;
string path; //记录递归过程中，每⼀步的决策

void dfs()
{
    if(path.size() == n)
    {
        cout << path << endl; //path存着前n个⼈的决策 
        return;
    }
    
    //不选
    path += 'N';
    dfs();
    path.pop_back(); //回溯：恢复现场
    
    //选
    path += 'Y';
    dfs(); 
    path.pop_back(); //回溯：恢复现场
}

int main()
{
    cin >> n;
    dfs();
    
    return 0;
}

2.组合型枚举

P10448 组合型枚举

解法：深搜

设 n = 4, m = 3，「从前往后」考虑 3 个位置应该选哪个数，我们可以画出如下决策树：

设计递归函数：

1. 重复子问题：当前这一位，应该放哪个数上去。因为这是一个「组合」问题，不涉及排列，所以我们当前位置开始放的数，应该是「上次决策的数的下一位」。
2. 实现方式参考代码和注释，结合「决策树」一起看会很清晰。

#include<iostream>
#include<vector>
using namespace std;

int n, m;
vector<int> path; //记录递归过程中，每⼀步的决策

void dfs(int pos)
{
    if(path.size() == m)
    {
        for(auto& e : path) cout << e << " ";
        cout << endl;
        return;
    }
    
    for(int i = pos; i <= n; i++)
    {
        path.push_back(i);
        dfs(i + 1);
        path.pop_back(); //回溯：恢复现场
    }
}

int main()
{
    cin >> n >> m;
    dfs(1);
    
    return 0;
}

3.枚举排列

B3623 枚举排列（递归实现排列型枚举）

解法：深搜

设 n = 3, k = 2，一共要选出两个数，可以依次「考虑要选出来的数」是谁，画出如下决策树：

设计递归函数：

1. 重复子问题：考虑这一位要放上什么数。因为是「排列」问题，所以我们直接从 1 开始枚举要放的数。
2. 剪枝：在这一条路径中，我们「不能选择之前已经选择过的数」，需要用到辅助数组。
3. 实现方式参考代码和注释，结合「决策树」一起看会很清晰。

#include<iostream>
#include<vector>
using namespace std;

const int N = 15;

int n, k;
vector<int> path; //记录递归过程中，每⼀步的决策
bool vis[N]; //辅助数组：标记哪些数已经选过 

void dfs()
{
    if(path.size() == k)
    {
        for(auto& e : path) cout << e << " ";
        cout << endl;
        return;
    }
    
    for(int i = 1; i <= n; i++)
    {
        if(vis[i] == false)
        {
            vis[i] = true;
            path.push_back(i);
            dfs();
            
            //回溯：恢复现场
            path.pop_back();
            vis[i] = false;
        }
    }
}

int main()
{
    cin >> n >> k;
    dfs();
    
    return 0;
}

4.全排列问题

P1706 全排列问题

解法：深搜

跟上一道题的决策一样，我们可以枚举每一位应该放上什么数，只不过少了 k 的限制。剪枝的策略还是一样的，那就是在路径中，「不能选择之前已经选过的数」。

#include<iostream>
#include<vector>
using namespace std;

const int N = 15;

int n;
vector<int> path; //记录递归过程中，每⼀步的决策
bool vis[N]; //辅助数组：标记哪些数已经选过

void dfs()
{
    if(path.size() == n)
    {
        for(auto& e : path) printf("%5d", e);
        cout << endl;
        return;
    }
    
    for(int i = 1; i <= n; i++)
    {
        if(vis[i] == false)
        {
            vis[i] = true;
            path.push_back(i);
            dfs();
            
            //回溯：恢复现场
            path.pop_back();
            vis[i] = false;
        }
    }
}

int main()
{
    cin >> n;
    dfs();
    
    return 0;
}