[인프런] 08_09 조합 구하기 (DFS)

📖  문제

---

설명

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

입력

• 첫 번째 줄에 자연수 N과 M이 주어집니다.

출력 

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

출력

 

 

⚠️  주의사항

---

• 중복된 조합은 제외
• 오름차순 출력

 

✍️  이해

---

/**
 * 고려해야 할 점 : 오름차순, 중복된 조합은 출력x
 * 1. 주어진 입력받기
 * 2. line == M 일때 출력
 * 3. for(i = startNum ~ <=N)
 *  3-1. answer[L] = i
 *  3-2. DFS(line + 1, startNum + 1)
 */

 

✏️  풀이

---

import java.util.Scanner;

public class Main {

    static int N, M, L;
    static int[] answer;
    public void DFS(int L, int S) {

        if (L == M) {
            for (int i : answer) System.out.print(i + " ");
            System.out.println();
        } else {
            for (int i = S; i <= N; i++) {
                    answer[L] = i;
                    DFS(L + 1, i + 1);
            }
        }

    }
    public static void main(String[] args) {

        Main T = new Main();

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        answer = new int[M];

        T.DFS(0, 1);
    }
}

---