AcWing 842. 排列数字
原题链接
简单
作者:
Tighanri
,
2023-11-26 10:59:17
,
所有人可见
,
阅读 50
运行程序看回溯递归详细流程
#include<iostream>
using namespace std;
const int N=10;
int path[N];
bool st[N];
int n;
void dfs(int u)
{
if(u==n+1)//当u==n+1时,说明已经到了第n+1层,搜索过了n个不同的数字,可以打印path
{
cout<<"已递归到最底层开始打印:";
for(int i=1;i<=n;++i)
cout<<path[i]<<" ";
cout<<endl;
return ;
}
for(int i=1;i<=n;++i)
{
if(!st[i])
{
cout<<"数字"<<i<<"之前并未递归过,开始递归"<<i<<endl;
st[i]=true;//在递归到最底层之前要保持标记状态,防止重复
cout<<"标记数字"<<i<<endl;
path[u]=i;
cout<<"把"<<i<<"装进path数组,并递归"<<u+1<<"层"<<endl;;
dfs(u+1);
cout<<"取消标记"<<i<<endl;
st[i]=false;//递归到最底层后取消标记因为不同的组合可以有相同的数字,同一个组合不可以有相同的数字
}
}
}
int main()
{
cin>>n;
cout<<"递归第一层"<<endl;
dfs(1);//从第一个数字开始搜索
return 0;
}