全排列(dfs)

1.题目链接
https://www.acwing.com/problem/content/844/

2.题意
给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法
现在,请你按照字典序将所有的排列方法输出

3.思路
如何用 dfs 解决全排列问题?
dfs 最重要的是搜索顺序。用什么顺序遍历所有方案。
对于全排列问题,以 n = 3 为例,可以这样进行搜索:
全排列(dfs)
用 path 数组保存排列,当排列的长度为 n 时,是一种方案,输出。
用 state 数组表示数字是否用过。当 state[i] 为 1 时:i 已经被用过,state[i] 为 0 时,i 没有被用过。
dfs(i) 表示的含义是:在 path[i] 处填写数字,然后递归的在下一个位置填写数字。
回溯:第 i 个位置填写某个数字的所有情况都遍历后, 第 i 个位置填写下一个数字

4.代码撰写

#include<bits/stdc++.h>

using namespace std;

int n;
const int N = 10;
bool st[N];
int path[N];

void dfs(int u){
    if(u == n){
        for(int i=0;i<n;i++){
            cout<<path[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=0;i<n;i++){
        if(!st[i]){
            path[u] = i + 1;
            st[i] = 1;
            dfs(u + 1);
            path[u] = 0;
            st[i] = 0;
        }
    }
}


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

上一篇:Cobalt Strike DLL用于永恒之蓝注入


下一篇:Dante,AES67,SMPTE ST 2110之间的关系