N과 M - 백트래킹 ( 종합 )

문제 1

package Baekjoon;


import java.util.Scanner;

//백준 N과 M (백 트래킹) - S3
public class ex15649 {
    static int n;
    static int m;
    static int[] ch;
    static int[] visit;

    public static void DFS(int L){
        if(L==m){
            for(int x : ch){
                System.out.print(x + " ");
            }
            System.out.println();
        }
        else{
            for(int i=1; i<=n; i++){
                if(visit[i]==0){
                    visit[i]=1;
                    ch[L]=i;
                    DFS(L+1);
                    visit[i]=0;
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        ch = new int[m];
        visit = new int[20];
        DFS(0);
    }
}

문제 2

package Baekjoon;

import java.util.Scanner;

public class ex15650 {
    static int n;
    static int m;
    static int[] ch;
    static int[] visit;

    public static void DFS(int L,int s){
        if(L==m){
            for(int x : ch){
                System.out.print(x + " ");
            }
            System.out.println();
        }
        else{
            for(int i=s; i<=n; i++){
                if(visit[i]==0){
                    visit[i]=1;
                    ch[L]=i;
                    DFS(L+1,i+1);
                    visit[i]=0;
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        ch = new int[m];
        visit = new int[20];
        DFS(0,1);
    }
}

문제 3

package Baekjoon;

import java.util.Scanner;

public class ex15651 {
    static int n;
    static int m;
    static int[] ch;
    static StringBuilder sb = new StringBuilder();

    public static void DFS(int L){
        if(L==m){
            for(int x : ch){
                sb.append(x+" ");
            }
            sb.append('\n');
        }
        else{
            for(int i=1; i<=n; i++){
                    ch[L]=i;
                    DFS(L+1);
                }
            }
        }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        ch = new int[m];
        DFS(0);
        System.out.println(sb);
    }
}

문제 4

package Baekjoon;


import java.util.Scanner;

public class ex15652 {
    static int n;
    static int m;
    static int[] ch; // 담는배열
    static StringBuilder sb = new StringBuilder();

    public static void DFS(int at,int L){
        if(L==m){
            for(int x : ch){
                sb.append(x+" ");
            }
            sb.append('\n');
        }
        else{
            for(int i=at; i<=n; i++){
                ch[L]=i;
                DFS(i,L+1);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        ch = new int[m];
        DFS(1,0);
        System.out.println(sb);
    }
}

문제 5

package Baekjoon;


import java.util.Arrays;
import java.util.Scanner;

// N과 M - S3
public class ex15654 {

    static int n;
    static int m;
    static int[] arr;
    static int[] ch; // 담는배열
    static boolean[] flag;
    static StringBuilder sb = new StringBuilder();

    public static void DFS(int L){
        if(L==m){
            for(int i=0; i<ch.length; i++){
                sb.append(ch[i] + " ");
            }
            sb.append('\n');
        }
        else{
            for(int i=0; i<arr.length; i++){
                // 가지고 있으면 출력안됨
                if(!flag[i]) {
                    flag[i]=true;
                    ch[L] = arr[i];
                    DFS(L+1);
                    flag[i]=false;
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        ch = new int[m];
        arr = new int[n];
        flag = new boolean[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr); // 오름차순 정렬

        DFS(0);
        System.out.println(sb);
    }
}

문제 6

package Baekjoon;


import java.util.Arrays;
import java.util.Scanner;

// 빽트래킹 - n 과 m
public class ex15655 {

    static int n,m;
    static int[] arr;
    static int[] ch;
    static boolean[] visit;

    public static void DFS(int s,int L) {
        if(L==m){
            for(int x : ch){
                System.out.print(x + " ");
            }
            System.out.println();
        }
        else{
            for(int i=s; i<n; i++){
                if(!visit[i]){
                    visit[i]=true;
                    ch[L]=arr[i];
                    DFS(i,L+1);
                    visit[i]=false;
                }

            }
        }
    }
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n];
        ch = new int[m];
        visit = new boolean[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        DFS(0,0);
    }
}

문제 7

package Baekjoon;

import java.util.Arrays;
import java.util.Scanner;

public class ex15656 {

    static int n,m;
    static int[] arr;
    static int[] ch;
    static StringBuilder sb = new StringBuilder();

    public static void DFS(int L){
        if(L==m){
            for(int x : ch){
                sb.append(x + " ");
            }
            sb.append("\n");
        }
        else{
            for(int i=0; i<n; i++){
                ch[L]=arr[i];
                DFS(L+1);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n];

        for(int i=0; i<n; i++) arr[i]=sc.nextInt();
        ch = new int[m];

        Arrays.sort(arr);
        DFS(0);

        System.out.println(sb);

    }
}

문제 8

package Baekjoon;


import java.util.Arrays;
import java.util.Scanner;

// 빽트래킹 - n과 m
public class ex15657 {
    static int n;
    static int m;
    static int[] arr;
    static int[] ch;

    public static void DFS(int s,int L){
        if(L==m){
            for(int x : ch){
                System.out.print(x + " ");
            }
            System.out.println();
        }
        else{
            for(int i=s; i<n; i++){
                ch[L]=arr[i];
                DFS(i,L+1);
            }
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        arr = new int[n];
        ch = new int[m];

        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);

        DFS(0,0);

    }
}

문제 9

package Baekjoon;

import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Scanner;

public class ex15663 {

    static int n,m;
    static int[] arr;
    static int[] ch;
    static boolean[] visit;
    static LinkedHashSet<String> set = new LinkedHashSet<>();


    public static void DFS(int L){
        if(L==m){
            StringBuilder sb = new StringBuilder();
            for(int x : ch){
                sb.append(x + " ");
            }
            set.add(sb.toString());
        }
        else{
            for(int i=0; i<n; i++){
                if(!visit[i]){
                    visit[i]=true;
                    ch[L]=arr[i];
                    DFS(L+1);
                    visit[i]=false;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }

        ch = new int[m];
        visit = new boolean[n];
        Arrays.sort(arr);
        DFS(0);
        for(String s : set){
            System.out.println(s);
        }
    }
}

문제 10

package Baekjoon;

import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Scanner;

public class ex15664 {

    static int n;
    static int m;
    static int[] arr;
    static int[] ch;
    static boolean[] visit;
    static LinkedHashSet<String> set = new LinkedHashSet<>();

    public static void DFS(int L,int s){
        if(L==m){
            StringBuilder sb = new StringBuilder();
            for(int x : ch){
                sb.append(x + " ");
            }
            set.add(sb.toString());
        }
        else{
            for(int i=s; i<n; i++){
                if(!visit[i]){
                    visit[i]=true;
                    ch[L]=arr[i];
                    DFS(L+1,i+1);
                    visit[i]=false;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n=sc.nextInt();
        m=sc.nextInt();

        arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }

        ch = new int[m];
        visit = new boolean[n];

        Arrays.sort(arr);
        DFS(0,0);

        for(String s : set){
            System.out.println(s);
        }
    }
}

문제 11

package Baekjoon;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Scanner;

public class ex15665 {

    static int n,m;
    static int[] arr;
    static int[] ch;
    static LinkedHashSet<String> set = new LinkedHashSet<>();

    public static void DFS(int L){
        if(L==m){
            StringBuilder sb = new StringBuilder();
            for(int x : ch){
                sb.append(x + " ");
            }
            set.add(sb.toString());
        }
        else{
            for(int i=0; i<n; i++){
                ch[L]=arr[i];
                DFS(L+1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        arr =  new int[n];
        ch =  new int[m];

        for(int i=0; i<n; i++){
            arr[i]=sc.nextInt();
        }
        Arrays.sort(arr);

        DFS(0);
        for(String s : set){
            System.out.println(s);
        }
    }
}

문제 12

package Baekjoon;

import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Scanner;

public class ex15666 {

    static int n,m;
    static int[] arr;
    static int[] ch;
    static boolean[] visit;
    static LinkedHashSet<String> set = new LinkedHashSet<>();
    public static void DFS(int s,int L){
        if(L==m){
            StringBuilder sb = new StringBuilder();
            for(int x : ch){
                sb.append(x + " ");
            }
            set.add(sb.toString());
        }
        else{
            for(int i=s; i<n; i++){
                ch[L]=arr[i];
                DFS(i,L+1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        arr = new int[n];
        ch = new int[m];
        visit = new boolean[n];
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        DFS(0,0);

        for(String x : set){
            System.out.println(x);
        }

    }
}