[Ch.08 - DFS] 11. 조합 구하기

조합 구하기
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

---

N개 중에 M개를 뽑는다. -> nCm

중복 X, 순서 존재 X

arr[2]

chk[2]

 

chk[i]=1;
arr[L]i;
DFS(L+1);
chk[i]=0;

-> chk[i]에 체크 한후, DFS를 돌려 확인한 다음, chk[i]에 체크 해제

 

public void DFS(int L){
 if(L==n){
  for(int x : arr){
   System.out.println(x+" ");
  }
 }
 else{
  for(int i=0;i<n;i++){
   if(chk[i]==0){
    chk[i]=1;
    arr[L]=i;
    DFS(L+1);
    chk[i]=0;
   }
  }
 }
}

---

package advdfsbfs.ch08;

import java.util.Scanner;

//조합 구하기
//N까지의 수가 적힌 구슬
//N개의 구슬 중에 M개의 구슬을 뽑는다.
//nCm
class Advdfsbfs09 {
	static int m,n;
	static int[] arr;
	static int[] pm;
	public void DFS(int L,int S) {
		if(L==m) {
			for(int x:pm) {
				System.out.print(x+" ");
			}
			System.out.println();
		}
		else {
			for(int i=S;i<=n;i++) {
				pm[L]=i;
				//배열의 L번째가 i가 되면, 오름차순 순서대로 정렬가능 
				DFS(L+1, i+1);
				//반복문이 S부터 시작하므로, 순서 상관없이 한번만 사용가능 -> i+1을 인수로 전달
			}
		}
		
		
	}
	public static void main(String[] args) {
		Advdfsbfs09 T =new Advdfsbfs09();
		Scanner kb =new Scanner(System.in);
		n=kb.nextInt();
		m= kb.nextInt();
		pm=new int[m];
		T.DFS(0,1);
	}
	

}