DFS--

数字的全排列

#include <bits/stdc++.h>
using namespace std;//最大的排列数目
const int N=10;
int n;
//存储排列的路径
int path[N];
//标记数字是否已经被使用
bool st[N];void dfs(int u){//到达递归边界，输出一个排列if(u==n){//输出循环for(int i=0; i<n; i++){cout<<path[i];}//不写return会继续往下走return;}//生成排列的主循环//遍历每个可能的数for(int i=1; i<=n; i++){//如果当前数字i没有被使用过if(!st[i]){//选择这个数放在当前位置upath[u]=i;//标记这个数已使用st[i]=true;//递归处理下一个位置dfs(u+1);//取消标记（回溯）st[i]=false;}}
}int main(){cin>>n;dfs(0);return 0;
}

语句的执行顺序分析

两点说明：
①u 的回退是由递归栈的结构自动处理的，不需要显式地进行 u-- 操作。
②等递归函数执行完后（也就是 return 了），程序才会执行st[i]=false;