백트래킹(N과 M - 1~4)

[N과 M(1) - 15649]

• 순열
• 뽑았던 카드는 다시 뽑을 수 없음

 

 

[N과 M(2) - 15649]

• 조합
• 뽑았던 카드는 다시 뽑을 수 없음

 

[N과 M(3) - 15649]

• 순열
• 뽑았던 카드는 다시 뽑을 수 있음

 

[N과 M(4) - 15649]

• 조합
• 뽑았던 카드는 다시 뽑을 수 있음

<N과 M(1)>

//N과 M (1)
import java.util.Scanner;

public class Problem_15649 {
    static int N, M;
    static boolean[] checked;
    static StringBuilder sb;
    static int[] arr;

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

        int count = 0;
        //sb = new StringBuilder("");
        doProcess(count);
    }

    private static void doProcess(int count) {
        if(count == M){
            for(int c=0; c<count; ++c){
                System.out.print(arr[c] + " ");
            }
            System.out.println();

            /*String tmp = sb.toString();
            for(int s=0; s<tmp.length(); ++s){
                System.out.print(tmp.substring(s, s+1) + " ");
            }
            System.out.println();*/
            return;
        }

        for(int i=1; i<=N; ++i){
            if(!checked[i]){
                checked[i] = true;
                //sb.append(i);
                arr[count] = i;

                doProcess(count+1);

                checked[i] = false;
                //sb.deleteCharAt(sb.length()-1);
            }
        }
    }
}

 

<N과 M(2)>

//N과 M (2)
import java.util.Scanner;

public class Problem_15650 {
    static int N, M;
    static boolean[] checked;
    static int[] arr;

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

        int start = 1;
        int count = 0;
        doProcess(start, count);
    }

    private static void doProcess(int index, int count) {
        if(count == M) {
            for(int c=0; c<count; ++c){
                System.out.print(arr[c] + " ");
            }
            System.out.println();
            return;
        }

        for(int i=index; i<=N; ++i){
            if(!checked[i]){
                checked[i] = true;
                arr[count] = i;

                doProcess(i, count+1);

                checked[i] = false;
            }
        }
    }
}

 

 

<N과 M(3)>

//N과 M (3)
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Problem_15651 {
    static int N, M;
    static boolean[] checked;
    static int[] arr;
    static BufferedWriter bw;

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = scanner.nextInt();
        M = scanner.nextInt();
        checked = new boolean[N+1];
        arr = new int[M];

        int count = 0;
        doProcess(count);

        bw.flush();
        bw.close();
    }

    private static void doProcess(int count) throws IOException {
        if(count == M){
            for(int c=0; c<count; ++c){
                bw.write(arr[c] + " ");
            }
            bw.write("\n");
            return;
        }

        for(int i=1; i<=N; ++i){
            arr[count] = i;
            doProcess(count+1);
        }
    }
}

 

 

<N과 M(4)>

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

public class Problem_15652 {
    static int N, M;
    static int[] arr;
    static BufferedReader br;
    static BufferedWriter bw;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        String input = br.readLine();
        st = new StringTokenizer(input, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[M];

        int start=1;
        int count=0;
        doProcess(start, count);

        br.close();
        bw.flush();
        bw.close();
    }

    private static void doProcess(int index, int count) throws IOException {
        if(count == M){
            for(int c=0; c<count; ++c){
                bw.write(arr[c] + " ");
            }
            bw.write("\n");
            return;
        }

        for(int i=index; i<=N; ++i){
            arr[count] = i;
            doProcess(i, count+1);
        }
    }
}