排列数字可以说是最基础的DFS了
第一次接触的时候还是在《啊哈 算法》那本书里
不过那时候才刚上大学什么都不懂
现在再写这题才真正理解
C++ 代码
#include<iostream>
using namespace std;
int n; //需要搜索的个数
const int N=10;
int path[N]; //path[]用于保存路径
bool st[N]; //用于记录 该步是否已经走过
void dfs(int u)
{
if(u==n) //一条路搜索完成
{
for(int i=0;i<n;i++) //输出结果
{
cout<<path[i]<<' ';
}
cout<<endl;
return;
}
for(int i=1;i<=n;i++) //未搜素完成则继续尝试 即一条走到底为止
{
if(!st[i])
{
st[i]=true; //标记当前步防止重复
path[u]=i; //保存当前路径
dfs(u+1); //进行下一步搜索
st[i]=false; //恢复现场 否则会影响下一条路的搜索
path[u]=0;
}
}
}
int main()
{
cin>>n;
dfs(0); //从第0个位置开始搜索
return 0;
}
还是不懂咋回溯的,12咋到13的
第一条路输出
123
后,它会回到for循环(i = 3),然后将3标记去除,for循环结束,回到上一个for循环,将2的标记去掉,此时i=2,for循环没有结束,会进行下一次for循环即i=3;然后重点来了,此时的u=1,i=3,它会去确定第2位,而i=3,即13
;建议结合搜索树
看卧槽,终于懂了
完了, 我来复习了hh
tql
懂了懂了,重点部分模拟了下就懂了,感谢
请问回到i= 3的时候它的标记是怎么去掉的呢
写的不错