AcWing 842. 排列数字（DFS）

# 排列数字 - 深度优先遍历 DFS

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int path[N];
bool st[N];

void dfs(int u){
	if(u == n){
		for(int i = 0; i < n; i++) printf("%d ", path[i]);
		puts("");
		return;
	}
	//u < n
	for(int i = 1; i <= n; i++){
		if(!st[i]){
			path[u] = i;
			st[i] = true;
			dfs(u + 1);
			path[u] = 0;
			st[i] = false;
		}
	}
}
int main(){
	cin >> n;
	dfs(0);
	return 0;
}

![[Pasted image 20221225142051.png]]
DFS 和递归没有必要区分太开 没有必要区分它们之间的关系
！[[Pasted image 20221225143121.png]]

#include <iostream>

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++) printf("%d ", path[i]);
        
        printf("\n");
        return;
    }
    for(int i = 1; i <= n; i++){
        if(!st[i]){
            path[u] = i;//将i放到当前位置上去
            st[i] = true;//记录一下这个数已经被用过了
            dfs(u + 1);//状态处理好之后递归到下一层
            
            
            //恢复现场
            // path[u] = 0;//这一段没有必要 因为递归到下一层path[u]在上面一定会被覆盖掉 所以不管是几都没问题
            st[i] = false;
        }
    }
}

int main(){
    cin >> n;
    
    dfs(0);
    
    return 0;
}