842. 排列数字

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

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

输入格式

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

输出格式

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

数据范围

1≤n≤71≤n≤7

输入样例：

3

输出样例：

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

题解(dfs)

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {
    public static int N = 10;
    public static int path[] = new int[N];
    public static boolean st[] = new boolean[N];
    public static int n;
    public static  BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args)throws Exception {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        dfs(0);
        bw.flush();
    }

    public static void dfs(int u) throws Exception{
        if ( u == n) {
            for (int i = 0; i < n; i++) {
                bw.write(path[i]+" ");
                //System.out.printf("%d ",path[i]);
            }
            bw.write("\n");
            //System.out.println();
        }

        for (int i = 1; i <= n; i++) {
            //判断i是否已经存在了
            if (!st[i]){
                //如果不存在则将则把i加入进去
                path[u] = i;
                //在把i标记一下
                st[i] = true;
                //继续判断下一个
                dfs(u + 1);
                //回潮，东西还原
                st[i] = false;
            }
        }
    }

}