백준 15663 N과 M(9)

문제

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

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

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

접근방식

솔직히 어려웠다... 결국 다른 분의 답을 보고 풀 수 있었다.
중요한 것은 이전의 값을 저장하는 변수지정, 이 수를 이미 사용했다는 check배열
이다. dfs문제들은 항상 이렇게 하면 풀릴것 같은데.. 하면서도 안풀리는 것 같다. (재귀 문제가 다 그런 것 같다.) 계속 많이 풀어보자

코드

#include <cstdio>
#include <algorithm>
using namespace std;
int N, M, res[8];
bool check[8];
void dfs(int x[], int k ){
	if(k == M){
		for (int i = 0; i < M; i++) 
			printf("%d ",res[i]);
		printf("\n");
		return;
	}
	int prev = -1;
	for (int i = 0; i < N; i++){
		if(!check[i] && (prev != x[i])){
			check[i] = true;
			prev = x[i];
			res[k] = x[i];
			dfs(x,k +1);
			check[i] = false;
		}
	}
}
int main(void){
	scanf("%d %d",&N,&M);
	int a[N];
	for (int i = 0; i < N; i++) scanf("%d",&a[i]);
	sort(a,a+N);
	dfs(a,0);
}