백준 15652번: N과 M (4) (C++)

문제 링크

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

15652번: N과 M (4)

 

중복을 허용하면서 감소하지 않는 수열로 만들어야 한다.

 

따라서 재귀를 이전 자리에 쓰인 숫자부터 진행하면 된다. 

 

첫번째 자리의 숫자를 정할 때, 이전에 쓰인 숫자가 없기 때문에, 이 경우에만 st를 1로 정해주면 된다.

#include<iostream>
using namespace std;
int N, M;
int arr[9];
void func(int k) {
	if (k > M) {
		for (int i = 1; i <= M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	int st = 1;
	if (k != 1) st = arr[k - 1];
	for (int i = st ; i <= N; i++) {
		
		arr[k] = i;
		func(k + 1);
	}
}
int main(void) {
	cin >> N >> M;
	func(1);
	return 0;
}