BOJ - 15650번_N과 M (2)

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

  • 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 출력한다.
  • 고른 수열은 오름차순이어야 한다.
  • 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

백트래킹을 이용한다.

이전 문제(BOJ - 15649번)과 풀이는 동일하다. 다만 수열이 오름차순이 되도록 if문에 조건(arr[num-1]<i)을 추가해준다.


소스코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
int arr[10];
bool check[10];

void func(int num) {
	if(num==M) {
		for(int i=0; i<M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n'; 
		return;
	}
	for(int i=1; i<=N; i++) {
		if(!check[i] && arr[num-1]<i) {
			arr[num] = i; 
			check[i] = 1;
			func(num+1);
			check[i] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	func(0);
}