[백준 15650] [백트래킹] [JAVA] N과M(2)

 

import java.util.Scanner;

public class Main {

    static int N;
    static int M;
    static boolean[] visited;
    static int[] answer;
    static StringBuilder ans = new StringBuilder();

    static void backtracking(int num){
        if(num==M){
            for(int i=0; i<M; i++){
                ans.append(answer[i]+" ");
            }
            ans.append("\n");
            return;
        }

        for(int i=1; i<=N; i++){
            if(!visited[i]){
                visited[i] = true;
                answer[num] = i;
                if(num!=0 && answer[num] < answer[num-1]){ // 15649번과의 차이: 지금 값이 앞에 있는 값보다 작을 때 다시 FOR문으로 돌아가기 
                    visited[i] = false;
                    continue;
                }
                backtracking(num+1);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        visited = new boolean[N+1];
        answer = new int[N+1];

        backtracking(0);

        System.out.println(ans);
    }
}