순열 구하기

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

 

▣ 입력설명

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다. 두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다.

 

▣ 출력설명

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

 

▣ 입력예제 1

3 2

3 6 9

 

▣ 출력예제 1

3 6

3 9

6 3

6 9

9 3

9 6

 

 

문제 분석

중복 없음 
순서 있음
→ 순열

* '중복 없음'을 체크하는 방법 :
- 체크 배열을 활용해서 ch[i] == 0 인 것만 뻗어 나갑니다.
- 사용 했으므로 ch[i] = 1로 바꿉니다.
- 백트래킹시 다시 ch[i] = 0 으로 복구해서 다음 for문에 영향을 끼치지 않도록 합니다. 

체크 배열을 제외하면 중복 순열과 코드가 같습니다. 

 

 

성공 코드

import java.util.Scanner;

public class Main {
	static int n,m;
	static int[] arr, pm, ch;
	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++) {
				// 체크배열 0인것만 뻗어나감
				if(ch[i] == 0) {
					// 사용했으므로 체크배열 1로 하고, 백트래킹때 0으로 복귀
					ch[i] = 1;
					pm[L] = arr[i];
					DFS(L+1);
					ch[i] = 0;
				}
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		ch = new int[n];
		pm = new int[m];
		arr = new int[n];
		// [ arr채우기 ]
		for(int i=0; i<n; i++) {
			arr[i] = kb.nextInt();
		}
		T.DFS(0); 
	}

}