[BOJ] 15652 N과 M(4)(백트래킹)

1. 문제

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

2. 풀이 과정

1) ⭕RIGHT⭕

• 코드

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> v;

void backtracking(int level)
{
	if (level == M)
	{
		for (int i = 0; i < v.size(); ++i)
			cout << v[i] << ' ';
		cout << '\n';
		return;
	}
	for (int i = 1; i <= N; ++i)
	{
		if (v.empty() || i >= v.back()) {
			v.push_back(i);
			backtracking(level + 1);
			v.pop_back();
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	backtracking(0);
	
	return 0;
}

• 추가 설명
  - N과 M(3)과 다른 부분
  N과 M(2)와 마찬가지로 고른 수열이 이전 수열보다 큰 경우만 탐색하므로,
  if (v.empty() || i >= v.back())를 통해 조건에 맞추어 수열을 살펴본다.