深搜回溯与不回溯的区别_深搜什么时候需要回溯

一、需要不断尝试以达到最终目的时需要回溯，比如数独、全排列。

以下为全排列代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string str;
string temp;
vector<bool> vis;
void dfs(int cnt,int n)
{
    if(cnt==n)
    {
        cout<<temp<<endl;
        return;
    }
    for(int i=0;i<n;i++)
    {
        if(vis[i]==false)
        {
            temp.push_back(str[i]);
            vis[i]=true;
            dfs(cnt+1,n);
            vis[i]=false;
            temp.pop_back();
        }
    }
}
int main()
{
    getline(cin,str);
    sort(str.begin(),str.end());
    int n=str.size();
    vis.resize(n);
    dfs(0,n);
    return 0;
}

搜完了回来了需要重置vis状态。

二、一锤子买卖时不需要回溯，比如图的深度优先遍历、二叉树节点间的最大距离问题。