例题背景

AcWing 823. 排列

分析

这题如果当$n=9$时，输出规模有$9\times9!=3,265,920$,如果一次一次输出必定会TLE
TLE代码：

import java.util.Scanner;

public class Main{
    public static void dfs(int n,int[] a,boolean[] st,int cur){
        if(cur==n+1)
        {
            for(int i=1;i<=n;i++)
                System.out.printf("%d ",a[i]);
            System.out.printf("\n");
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(!st[i])
                {
                    a[cur]=i;
                    st[i]=true;
                    dfs(n,a,st,cur+1);
                    st[i]=false;
                }
            }
        }
    }
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);

        int n=sc.nextInt();

        int[] a=new int[10];
        boolean[] st=new boolean[10];
        for(int i=0;i<10;i++)
            st[i]=false;

        dfs(n,a,st,1);
    }
}

直接使用了System.out.printf输出，当$n=9$时，调用了$9\times9!=3,265,920$次
输出量非常大
这时需要改进

改进方法/解决方案

效率较高，输出规模较大时使用，注意需要抛异常。

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
//一定要记得引入以上两个包
public class Main { //一定要记得抛出异常
    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write("Hello World\n");  //使用bw.write进行输出
        bw.flush();  // 需要手动刷新缓冲区
    }
}

应用在本题：

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

public class Main{
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void dfs(int n,int[] a,boolean[] st,int cur)throws Exception{
        if(cur==n+1)
        {
            for(int i=1;i<=n;i++)
                bw.write(a[i] +  " ");
            bw.write("\n");
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(!st[i])
                {
                    a[cur]=i;
                    st[i]=true;
                    dfs(n,a,st,cur+1);
                    st[i]=false;
                }
            }
        }
    }
    public static void main(String []args)throws Exception{
        Scanner sc=new Scanner(System.in);

        int n=sc.nextInt();

        int[] a=new int[10];
        boolean[] st=new boolean[10];
        for(int i=0;i<10;i++)
            st[i]=false;

        dfs(n,a,st,1);
        bw.flush();  //手动刷新缓冲区
    }
}