题目描述

给定集合{1~n}输出全排列

输入样例

3

输出样例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

算法1

(暴力枚举) $O(2^n2)$

思路和之前两题有所差异，这题直接放入还没有被放入过的数即可

C++ 代码

/*
    Name:AcWing 94. 递归实现排列型枚举
    Author:wyz
    Date:2019/4/2 10:27:42
    Note:

*/

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
int n;
vector<int> v;//用于记录当前的排列结果 
void dfs(int cur,int station){
    //cur表示当前已经有cur个数被排列 
    if(cur>n){//已经挑排列完了所有的数，结束递归
        for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
        cout<<endl;
        return;
    }
    //放入没有被排列的数 
    for(int i=0;i<n;i++){
        if(!(station>>i & 1)){//第i位(i+1)没有放入 
            v.push_back(i+1);//放入(i+1) 
            dfs(cur+1,station | 1<<i);//cur个数被排列完，对第cur+1个数进行排列 
            v.pop_back();//将之前放入的数取出 
        }
    }
    return; 

}
int main(){
    cin>>n;
    dfs(1,0);//已经排列了0个数，所有数都还没有被排列过 
    return 0;
}