整体理解,每次深搜都是在做同样的事情,在函数体内调用函数本身
每次遍历一下所有的数字,找到第一个没有使用的数字,写到路径上,继续往下搜
每次继续往下搜都会重新遍历一下所有的数字,找到第一个没有使用的数字,填到相应的路经下
一直搜到最深的地方,找到边界以后开始回溯,每次回溯,都会将标记最近的一次标记操作重置
每次重置完成以后会看看循环有没有结束,找到最近一个没有结束的循环,没有结束会继续循环,相当于往上走到父节点然后继续判断
在相同的路径位置,找到后面能使用的数字填上,然后继续向下搜索,然后回溯。
递归的整个过程分为深入和退回阶段
代码模拟,搜索的过程就像是一颗树
0到n有n+1个数,过程中做n次选择,相当于是找路径,每次到底n条路径
模拟过程
1.u=0,i=1,从根节点开始搜索。st[1]=false,path[0]=1修改为st[1]=true,dfs(1),继续调用函数,等待返回
2.u=1,i=1,i=2,st[1]=true不满足,st[2]=false,path[1]=2,st[2]=true,dfs(2),继续调用函数,等待返回
3.u=2,i=1,i=2,i=3,st[1]=true,st[2]=true,st[3]=false,path[2]=3,st[3]=true,dfs(3),满足边界条件输出1 2 3 并返回
4.返回时会继续往下执行st[3]=false
5.继续返回第二步dfs(2)下面,此时i=2,st[2]=false,因为第二次的循环没有结束,返回第二步,此时继续进行循环
u=1,i=3,st[3]=false满足,path[1]=3,st[3]=true表示用过。dfs(2),再次调用该函数,循环结束
6.u=2,i=1,i=2,st[1]=true不满足,st[2]=false,path[2]=2,st[2]=true,dfs(3),满足边界条件输出1 3 2 并返回 st[2] = false
7.返回第六步dfs(2),st[3]=false,此时循环结束,返回第一步,继续第一步后面的循环u=0,i=2
同理能够得到
2 1 3
2 3 1
3 1 2
3 2 1
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 10;
int n;
int path[N];//用来表示选择的组合
bool st[N];
//用bool数组来标记数字是否用过
//例如str[1]表示数字1已经用过不会再选
void dfs(int u)
{
//u代表搜索到的层数,当搜到第n层,代表搜索到最底部。
//当搜到了最底层,完成了一种排列组合,可以输出当前的这种组合。
//边界情况
if (u == n)
{
for (int i=0;i<n;i++) printf("%d ",path[i]);
puts("");//每次输出完一种组合以后,空一行
}
for (int i=1;i<=n;i++)
if (!st[i])//代表数字并没有用过
{
path[u] = i;//把i的值填到当前层数对应的位置
st[i] = true;//修改标记表示当前这个数已经用过
dfs(u+1);//继续往更深一层搜索
st[i] = false;
//会因为递归不断地调用dfs直到边界
//每次返回上一层函数后继续向后执行,保证每次标记都能重置为false
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}