[Inflearn] 자바 알고리즘 문제풀이 #08-09 9. 조합 구하기(DFS)

문제

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

 

 

입력 

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

 

출력 

첫 번째 줄에 결과를 출력합니다.

출력순서를 사전순으로 오름차순으로 출력합니다.

 

예시 입력 1 

4 2

예시 출력 1

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

 

 

 

내 풀이 = 선생님 풀이

import java.util.Scanner;

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

    public static void main(String[] args) {
        Main8_9 T = new Main8_9();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        combi = new int[m];
        T.DFS(0, 1);
    }
}

다음 DFS를 호출할 때 시작 숫자를 +1해서 파라미터로 같이 넘기는 방식 !

어떤 숫자를 썼는지 ch배열로 확인할 필요 없이 순서대로 돌고 끝내면 되는 간단한 코드이다.

 

 

 

결과