백트래킹DFS_백준 N과M(1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

package rhs;

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N,M;
    //used배열을 구현해서 사용한 수를 체크
    static int[] selected,used;

    static void input(){
        FastReader scan = new FastReader();
        N = scan.nextInt();
        M = scan.nextInt();
        selected = new int[M + 1];
    }

    public static void solution(int k){
        if(k == M + 1) { // M+1 번째를 선택하려고함 모두 선택하였다.
            for(int i = 0; i<= M; ++i)
                sb.append(selected[i]).append(' ');
            sb.append('\n');

        }else{
            for(int cand = 1; cand<=N; ++cand){
                //중복 체크부분
                if(used[cand] == 1) continue;

                    selected[k] = cand;
                    used[cand] = 1;
                    // 다음노드에 올 수 있는 수를 선택해주는 재귀함수호출
                    solution(k + 1);
                    //기존에 선택했던 k번째 배열 초기
                    selected[k] = 0;
                    //사용한 수를 초기화- 다음 재귀호출에서 정상동작위해 
                    used[cand] = 0;

            }
        }
    }
    public static void main(String[] args) {
            input();
            //첫번쨰 원소부터 M번째 원소를 중복허용하여 찾기
            solution(1);
            System.out.println(sb.toString());
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}