N 과 M 2

문제 링크

자연수 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; // 이미 사용된 문자라면 탐색하지 않음
		if(p > 1 && arr[p - 1] > i) 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;
}