[c++/백준] 15650번: N과 M (2)

문제 링크

15650번: N과 M (2)

풀이

백트래킹을 이용하는 문제

1. sequence의 cnt는 현재 수열의 개수, last는 현재 수열의 마지막 숫자, v는 현재 수열이다.
2. n-last가 m-cnt보다 크거나 같으면 m개의 수를 뽑을 수 있다는 뜻이므로 계속 진행한다.
3. cnt와 m이 같으면 m개의 수를 정상적으로 뽑았다는 것이므로 출력
4. 아니면 재귀호출로 계속해서 수를 뽑는다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;

void sequence(int cnt, int last, vector<int> v)
{
	if (n - last >= m - cnt) {
		if (cnt == m) {
			for (int i = 0;i < cnt;i++) {
				cout << v[i] << " ";
			}
			cout << "\n";
		}
		else {
			for (int i = last + 1;i <= n;i++) {
				vector<int> tmp = v;
				tmp.push_back(i);
				sequence(cnt + 1, i, tmp);
			}
		}
	}
}

int main()
{
	cin >> n >> m;

	for (int i = 1;i <= n;i++) {
		vector<int> tmp;
		tmp.push_back(i);
		sequence(1, i, tmp);
	}

	return 0;
}