Q. (X)

---

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

실패 요인

직전 i를 DFS()의 매개변수로 넘기면, m이 3일때 중복 발생함..

package codingTest;
import java.util.*;
class Main{
	static int[] arr;
	static int n, m;
	static int[] pm;
	public void DFS(int L, int idx){
		if(L == m){
			for(int x : pm) System.out.print(x+" ");
			System.out.println();
		}else{
			for(int i=0; i<n; i++){
				if(idx != i){
					pm[L] = arr[i];
					DFS(L+1, i);
				}
			}
		}
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt(); 
		arr=new int[n];
		m = kb.nextInt(); 
		pm = new int[m];
		for(int i=0; i<n; i++)arr[i]=kb.nextInt();
		T.DFS(0, -1);
	}
}

전략

• 중복 되지 않는 순열
  → ch배열 사용
• 트리 & 스택 그려보기
  

  스택(트리에 해당하는 현재 L값 + 복귀위치)이 머릿속에 그려지면 상태트리만 그려도됨!

정답

package codingTest;
import java.util.*;
class Main{
	static int[] arr, ch;
	static int n, m;
	static int[] pm;
	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 T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt(); 
		m = kb.nextInt(); 
		arr=new int[n];
		for(int i=0; i<n; i++)arr[i]=kb.nextInt();
		ch=new int[n];
		pm = new int[m];
		T.DFS(0);
	}
}