Recursion: 백준 N과 M(8)-15657

문제 유형

Recursion

작성 코드

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

// 백준 N과 M(8)-15657
public class Main {
    public static StringBuilder answer;
    public static int[] givenNums;
    public static int[] row;
    public static boolean[] checks;
    public static int N;
    public static int M;
    public static void recursive(int depth, int index){
        if (depth == M) {
            for (int element :  row) {
                answer.append(element).append(" ");
            }
            answer.append("\n");
            return;
        }
        for (int i = index; i < givenNums.length; i++) {
            if (!checks[i]) {
                row[depth] = givenNums[i];
                recursive(depth+1,i);
            }
        }
    }
    public static void input(){
        Scanner scanner = new Scanner(System.in);
        answer = new StringBuilder();
        N = scanner.nextInt();
        M = scanner.nextInt();

        checks = new boolean[N];
        row = new int[M];
        givenNums = new int[N];
        for (int i = 0; i < N; i++) {
            givenNums[i] = scanner.nextInt();
        }
        Arrays.sort(givenNums);
    }
    public static void main(String[] args) {
        input();
        recursive(0,0);
        System.out.println(answer);
    }
}

접근 방식

1. 이전의 Recursion문제에서 이제는 중복을 허용한 모든 조합을 반환함과 동시에 조합의 중복되서는 안된다. 

2. 그래서 이번에는 checks를 지우고 index를 활용해 각 조합의 중복을 방지했다.

개선 사항

솔직히 개선 할 부분이 없다. 단, 이런 문제의 활용이 핵심인거 같다.