[DFS] 조합 구하기 .java

문제

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

 

 

내 풀이

 

• combi 배열은 선택된 m개의 숫자를 저장하는 역할
• dfs(0, 1) 호출로 재귀를 시작 -> 여기서 0은 현재 깊이, 1은 시작 숫자

for문

• for (int i = s; i <= n; i++): s부터 n까지 반복하며 숫자를 선택. i는 선택된 숫자
• combi[L] = i: 현재 깊이에 숫자 i를 저장
• dfs(L + 1, i + 1): 깊이를 하나 증가시키고, 숫자는 i + 1부터 시작(중복 방지)

import java.util.Scanner;


public class Main {
    static int[] combi;
    static int n,m;

    public static void dfs(int L, int s) {
        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) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        combi = new int[m];
        dfs(0,1);



    }

}

 

 

💡💡

조합 코드는 자주 응용되기 때문에 틀을 외우자!!