21天学习挑战赛-1.回溯

​
​

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

回溯的概念（简单介绍）

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。 – 牛客

建议直接去代码随想录看
它的回溯三部曲，很不错的

代码随想录回溯

例题

1. acwing的全排列数字

acwing排列数字

#include<iostream>
#include<vector>
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 ;
}

2.牛客的全排列数字

无重复数字

class Solution {
public:
    bool b[1000];
    vector<vector<int>> res ;
    vector<int> path;
    int n ;
    void dfs(vector<int> &path , vector<int> x)
    {
        if(path.size() >= n){
            res.push_back(path);
            return ;
        }
        for(int i = 0 ; i < n ; i++)
        {
            if(!b[x[i]])
            {
                path.push_back(x[i]);
                b[x[i]] = true;
                dfs(path,x);
                path.pop_back();
                b[x[i]] = false ;
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
        n = num.size();
        dfs(path,num);
        return res ;
    }
};

3.牛客的有重复数字的全排列数字

有重复数字

class Solution {
public:
    vector<vector<int>> res;
    int n ;
    void dfs(vector<int>&num , vector<int>& path, vector<int> &vis)
    {
        if(path.size()>=n)
        {
            res.push_back(path);
            return ;
        }
        for(int i = 0 ; i < n ; i++)
        {
            if(vis[i]) continue;
            if(i>0 && !vis[i-1] && num[i] == num[i-1]) continue ;
            if(!vis[i])
            {
                path.push_back(num[i]);
                vis[i] = 1 ;
                dfs(num ,path, vis);
                path.pop_back();
                vis[i] = 0;
            }
            
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(),num.end());
        n = num.size();
        vector<int>path;
        vector<int>vis(n,0);
        dfs(num,path,vis);
        return res;
    }
};

4.牛客的有重复字母的全排列字母

​字符串全排列

class Solution {
public:
    vector<string> res;
    string temp ;
    int n ;
    void dfs(string &str,string &temp,vector<int> & vis)
    {
        if(temp.size() >= n)
        {
            res.push_back(temp);
            return ;
        }
        for(int i = 0 ; i < n ; i++)
        {
                if(vis[i]) continue;
                if(i>0 && !vis[i-1] && str[i] == str[i-1]) continue ;
            if(!vis[i])
            {
                vis[i] = 1;
                temp.push_back(str[i]);
                dfs(str,temp,vis);
                vis[i] = 0 ;
                temp.pop_back();
            }
                
        }
    }
    vector<string> Permutation(string str) {
        n = str.size();
        vector<int>vis(n,0);
        dfs(str,temp,vis);
        return res;
    }
};