[백준 15649] N과 M(1)

요구사항

combination 구현

 

풀이

백트래킹을 이용하여 항상 앞에서 부터 방문했는지 검사해가며 체크한다

 

매일 구현하던 방법으로 구현하였을때 오름차순으로 되지 않아 약간 힘들었다

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int visit[10];
int map[10];
int n, m;
vector<int> v;
void com(int now, int cnt, int want) {
	if (cnt == want) {
		for (int i = 0; i < want; i++) {
			printf("%d ", v[i]);
		}
		printf("\n");
		return;
	}
	for (int i = 0; i < n; i++) {
		if (visit[i] == 1) continue;
		visit[i] = 1;
		v.push_back(map[i]);
		com(i + 1, cnt + 1, want);
		visit[i] = 0;
		v.pop_back();
	}
	
}
void swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
void per(int now, int cnt) {
	if (cnt == m) {
		for (int i = 0; i < cnt; i++) {
			printf("%d ", map[i]);
		}
		printf("\n");
		return;
	}
	for (int i = 0; i < n; i++) {
		if (visit[i] == 1) continue;
		visit[i] = 1;
		swap(&map[i], &map[cnt]);
		per(now+1,cnt+1);
		visit[i] = 0;
		swap(&map[i], &map[cnt]);
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		map[i] = i + 1;
	}
	//per(0, 0);
	com(0, 0, m);
}