백준 15650번
https://www.acmicpc.net/problem/15650

---

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

---

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

---

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

생각하기

앞에서 풀었던 N과 M(1) 문제와 같은 Backtracking과 사용한 문제이다

N과 M(1)에서 출력값에서 차이점을 보자면
N과 M(2)는 중복되는 값이 허용되었다.

예를 들면
2 1과 1 2는 다른 값으로 보고 위치에 따른 중복되는 경우도 모두 탐색하는 것이 었지만 N과 M(2)는 중복은 제외한다 1 2 와 2 1은 같은 값으로 본다는 차이점이 있다.

동작

이번에는 방문을 확인하는 visit배열이 없고, 대신 현재 위치를 확인하는 at변수가 새로 생겼다.

시작 값이 1이기 때문에 at은 1로 시작하고 배열의 index값으로 사용하기 위한 depth는 0부터 때문에, DFS(1, 0)으로 시작한다.

N과 M이 4 4라고 했을 때 동작을 보자.

at값이 i값이 되어 반복을 시작한다.

1. DFS(1, 0) 실행 -> arr[0] = 1

2. DFS(2, 1) 실행 -> arr[1] = 2

3. DFS(3, 2) 실행 -> arr[2] = 3

4. DFS(4, 3) 실행 -> arr[3] = 4

5. DFS(5, 4) 실행 -> if(M == 4 == depth) 조건에 걸리게 되고
   arr = [1, 2, 3, 4] 배열의 값이 모두 출력되어 StringBuilder에 append 된고 return 된다.

6. 다시 DFS(4, 3)으로 돌아온다. -> i = 4이므로 증가할 수 없어서 곧바로 return된다.

7. DFS(3, 2)으로 돌아온다. -> i = 4로 실행된다. DFS( i+1, depth +1 )

...

다시 돌아오는 이 과정이 반복되지만
이후로 if(M == 4 == depth) 조건에 한번도 걸리지 않기 때문에 더 이상 출력은 되지 않는다.

TMI

재귀는 진짜 많이해봐도 이해가 어렵고 힘들다..

재귀는 손맛이지

---

코드

import java.util.*;
import java.io.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, M;
	static int arr[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken()); 

		arr = new int[M];

		DFS(1, 0);
		System.out.println(sb);
	} // End of main

	static void DFS(int at, int depth) {
		
		if(depth == M) {
			for(int val : arr) {
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}

		for(int i=at; i<=N; i++) {
			arr[depth] = i;
			DFS(i + 1, depth + 1);
		}

		return;
	} // End of DFS

} // End of class