算法1

STL next_permutation

第一种采用C++ STL中的next_permutation进行全排列

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int main(){

    int n;
    cin >> n;
    vector<int> v;
    for(int i = 1; i <= n; i++){
        v.push_back(i);
    }
    do{
        for(int i = 0; i < n; i++){
            printf("%d ", v[i]);
        }
        puts("");
    }while(next_permutation(v.begin(), v.end()));
    return 0;
}

算法2

递归求解

第二种使用递归的方式求解
画出递归树,将递归树转换成代码

时间复杂度

$O(n!)$

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

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

void dfs(int v){
    if(v > n){
        for(int i = 1; i <= n; i++){
            printf("%d ", st[i]);
        }
        puts("");
    }
    for(int i = 1; i <= n; i++){
        if(!used[i]){
            used[i] = true;
            st[v] = i;
            dfs(v+1);
            used[i] = false;
        }
    }
}

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