백준 15657번: N과 M (8) (C++)

https://www.acmicpc.net/problem/15657

15657번: N과 M (8)

 

사용할 수 있는 수들을 오름차순 정렬한다.

 

이전 자리에서 사용한 숫자보다 다음에 사용할 자리의 숫자가 크거나 같으면 된다.

 

숫자를 중복해서 사용할 수 있으니, 숫자의 사용 여부를 관리하는 배열도 필요하지 않다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int num[9], arr[9];
int n, m;
void func(int k) {
	if (k == m + 1) {
		for (int i = 1; i <= m; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= n; i++) {
		if (arr[k - 1] > num[i]) continue; //k가 1이면 arr[] = 0 이라서 상관X
		else {
			arr[k] = num[i];
			func(k + 1);
		}
	}
}
int main(void) {
	
	cin >> n >> m;
	//n개 가지고 길이 m
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	sort(num + 1, num + 1 + n);
	func(1);
	return 0;
}