[백준 15649 JAVA 자바] N과 M (1)

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열입니다

 

nCm을 사전 순으로 증가하는 순서로 출력합시다

 

이럴때는 깊이탐색을 이용해야합니다

깊이 탐색을 이용해서

모든 경우를 차례대로 조사합니다

 

코드입니다

import java.util.Scanner;

public class Main {
	
	static int[] arr;
	static boolean[] visit;

	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		 
		int m = scan.nextInt();
		int n = scan.nextInt();
		
		arr = new int[n];
		visit = new boolean[m];
		dfs(m, n, 0);
    }
	static void dfs(int m, int n, int depth) {
		if (depth == n) {
			for (int val : arr) {
				System.out.print(val + " ");
			}
			System.out.println();
			return;
		}
		for (int i=0; i<m; i++) {
			if (!visit[i]) {
				visit[i] = true;
				arr[depth] = i+1;
				dfs(m, n, depth + 1);
				visit[i] = false;
			}
		}
	}
}

깊이 탐색은

boolean visit[]을 이용해서

내가 지나왔나 를 판단합니다