[알고리즘] 백트래킹

이론정리

문제풀이

//N과 M(1)과의 차이점은 오름차순만 된다는거
//그러면 backtracking할때마다 이전 수가 뭐였는지만 알면
//그것보다 높은 수 안에서만 수열 만들면 되니까 파라미터값으로 넘겨주기

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> num;

void backtracking(int cnt, int prev) {
	if (cnt == m) {
		for (int i = 0; i < cnt; i++) {
			cout << num[i] << ' ';
		}
		cout << "\n";
		return;
	}

	for (int i = prev+1; i <= n; i++) {
		num[cnt] = i;
		backtracking(cnt + 1, i);
	}
}

int main() {
	cin >> n >> m;
	num.assign(m, 0);

	backtracking(0, 0);

}