[Algorithm]알고리즘 자바_61 조합 구하기

 

💬 문제 설명

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

 

 

✨ 아이디어

​

DFS(Level, start)로 재귀를 진행하자. start의 크기를 매번 매번 감소 시키면서 나를 배제시킨다.

 

 

💻 Solution.java

import java.util.*;

public class Main {
	static int n, m;
	static int[] combi;
	
	public 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){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		
		combi = new int [m];
		
		main.DFS(0, 1);
		sc.close();
		return ;
	}
}