[Algorithm]알고리즘 자바_59 순열 구하기 (DFS)

 

💬 문제 설명

100이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

 

 

🔨 입출력 예

 

입력 - 첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N)이 주어집니다.

두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다.

3 2
3 6 9

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

3 6 
3 9 
6 3 
6 9 
9 3 
9 6

 

 

💻 Solution.java

import java.util.*;

public class Main {
	static int[] pm, ch, arr;
	static int n, m;
	
	public void DFS(int L) {
		if(L == m) {
			for(int x: pm) System.out.print(x+" ");
			System.out.println();
		}
		else {
			for(int i = 0; i < n; i++) {
				if(ch[i] == 0) {
					ch[i] = 1;
					pm[L] = arr[i];
					DFS(L + 1);
					ch[i] = 0;
				}
			}
		}
 	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); 
		m = sc.nextInt();
		arr = new int[n];
		
		for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
		
		ch = new int [n];
		pm = new int [m];
				
		main.DFS(0);
		sc.close();
		return ;
	}
}