조합 구하기(DFS, 재귀, 조합)

문제설명

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.

입력 설명

• 첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
  
  

출력 설명

• 첫 번째 줄에 결과를 출력합니다.
• 출력순서는 사전순으로 오름차순으로 출력합니다.

입력예제

4 2

출력예제

1 2
1 3
1 4
2 3
2 4
3 4

내 코드

import java.util.Scanner;

public class Main_8_9 {
    static int n;
    static int r;
    static int[] arr;

    void dfs(int lv, int s){
        if(lv == r){
            for(int x : arr){
                System.out.print(x + " ");
            }
            System.out.println();
        }
        else{
            for(int i = s; i <= n; i++){
                arr[lv] = i;
                dfs(lv+1, i+1);
            }
        }
    }

    public static void main(String[] args) {
        Main_8_9 t = new Main_8_9();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        r = kb.nextInt();
        arr = new int[r];

        t.dfs(0, 1);
    }
}

• DFS를 활용하여 풀어보았다.
• arr 배열을 통해 출력 값을 저장한다.
• lv는 배열의 인덱스를 의미한다.(lv == r에서 출력을 하게 되는데 그 전까지 r크기인 배열을 채워놓는다.)