N 과 M 1

문제 링크

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

숫자 사용에 중복이 없어야 한다는 제약 조건이 있다. 스도쿠 문제에서처럼 숫자 사용 여부를 저장하며 순회하는 방식으로 해결 할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> ch/*숫자 사용 여부*/, arr/*완성된 수열*/;
int n, m;
void r(int p) {
	if(p > m) { // 끝까지 탐색한 경우
		for(int i=1;i<=m;i++) {
			cout << arr[i] << " ";
		}
		cout << "\n";
		return; // 지금까지 저장된 문자열 출력하고 탐색 종료
	}
	for(int i=1;i<=n;i++) {
		if(ch[i] == 1) continue; // 이미 사용된 문자라면 탐색하지 않음
		ch[i] = 1; // 사용 표시
		arr[p] = i; // 현재 위치에 i라는 숫자 사용
		r(p + 1); // 다음 위치 탐색
		ch[i] = 0;
	}
}
int main() {
	cin >> n >> m;
	ch = vector<int>(n + 1); arr = vector<int>(m + 1);
	r(1);
	return 0;
}