백준 10974번 모든 순열 JAVA

링크텍스트

설명

백준 15649번 N과 M (1)과 똑같은 문제이다. 백트래킹 사용하면 된다.
시간복잡도: O(N!), 공간복잡도: O(N!)

코드

import java.util.*;
import java.io.*;

class Main {

        static int n;
        static int [] arr;
        static boolean [] check;
        static StringBuilder sb = new StringBuilder();
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    n = Integer.parseInt(br.readLine());
	    
	    arr = new int[n];
        check = new boolean[n];
	    
	    dfs(0);
        System.out.print(sb);

	}
	
	public static void dfs(int depth){
	    if(depth==n){
            for(int i=0;i<n;i++){
                sb.append(arr[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        for(int i=0;i<n;i++){
            if(!check[i]){
                check[i] = true;
                arr[depth] = i+1;
                dfs(depth+1);
                check[i] = false;
            }
        }
	}
}