[BOJ] 15652 - N 과 M (4)

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

---

[알고리즘풀이]

중복은 허용되지만, 오름차순으로 뽑아야하므로 가장 마지막에 담긴 원소를 넘겨주며 백트레킹 기법을 구현한다.

#include<iostream>
#include<vector>

using namespace std;

int m, n;

void bt(int, int, vector<int>);

int main(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		vector<int> v;
		v.push_back(i);
		bt(1, i, v);
		v.pop_back();
	}
}

void bt(int count, int start, vector<int> v) {
	if (count == m) {
		for (int i = 0; i < m; i++)
			cout << v[i] << ' ';
		cout << '\n';
		return;
	}
	for (int k = start; k <= n; k++) {
		v.push_back(k);
		bt(count + 1, k, v);
		v.pop_back();
	}
}

---