回溯 -- 21天学习挑战赛第一天

​
​

活动地址：CSDN21天学习挑战赛

什么是回溯？

1. 回溯的基本定义

回溯，计算机算法。回溯法也称试探法，它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。

2. 回溯的应用场景

回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现。
dfs
组合，全排列，N皇后问题

回溯例题套餐（实战！）

1. 组合数

（1）组合数，力扣77题
这道题就是最基本的回溯问题，初始状态就是1，然后遍历到有两个数的时候达到终止条件，存入结果并return，这个时候重要的来了：
在dfs（）函数return之后，要恢复之前的状态，这道题就是temp的弹出末尾元素

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp ;
    vector<bool> vis;
    int n ;
    void dfs(int x , int k)
    {
        if(temp.size() >= k)
        {
            ans.push_back(temp);
            return ;
        }
        for(int i = x; i <= n ; i++)
        {
                temp.push_back(i);
                dfs(i+1,k);
                temp.pop_back();    
        }
    }
    vector<vector<int>> combine(int a, int k) {
        n = a ;
        dfs(1,k);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

还有一系列更难的组合题，可以搜一下力扣题目：组合

2. 全排列

​acwing 842 排列数字

dfs(1) 从一开始，在dfs用一个for循环遍历，用一个b【】布尔数组来存是否放入vector，放入就变为true，递归回来的时候再恢复为false

#include
#include
using namespace std;
const int N = 10 ;
int n ;
int b[N];
vector<int>q;
void dfs(int x)
{
    if(q.size() >= n)
    {
        for(auto x : q) cout << x << " " ;
        cout << endl;
        return ;
    }
    for(int i = 1  ; i <=n ; i++)
    {
        if(!b[i])
        {
            q.push_back(i);
            b[i] = true ;
            dfs(i+1);
            b[i] = false ;
            q.pop_back();
        }
        
    }
}
int main()
{
    cin >> n ;
    dfs(1);
    return 0 ;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

如果能帮助到大家的话，可以留下您宝贵的赞嘛，如果有任何问题都可以评论区或者私信我哦