题目描述

给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数n。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤7

输入样例：

3

输出样例：

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

C ++代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10;

int ways[N];//临时记录方案
bool st[N];//标记数字是否用过,若用过则标记为true,反之标记为false.
int n;

void dfs(int u){
    if(u >= n){
        for(int i = 0; i < n; i ++) cout << ways[i] << ' ';//输出方案
        puts("");
        return ;
    }

    for(int i = 1; i <= n; i ++){
        if(!st[i]){
            ways[u] = i;//记录方案
            st[i] = true;//标记当前数字已用
            dfs(u + 1);//递归搜索下一层

            //回溯过程
            ways[u] = 0;//可省略,因为ways[u]会不断被覆盖
            st[i] = false;//不可省
        }
    }
}

int main(){
    cin >> n;

    dfs(0);//从第下标为0的位置开始暴搜

    return 0;
}