[C++] 백준 15650: N과 M (2)

문제

[C++] 백준 15650: N과 M (2) SILVER 3
https://www.acmicpc.net/problem/15650

 

---

 

접근 방법

1부터 N까지 중에서 M개를 고르는 조합(오름차순) 을 모두 출력하는 문제다.
순서가 바뀐 경우는 같은 조합으로 취급하므로(예: 1 2와 2 1은 같은 조합), 항상 작은 수부터 큰 수로만 뽑히도록 백트래킹을 구성하면 된다.

이를 위해 start 변수를 사용해, 다음에 뽑을 수 있는 숫자의 시작 범위를 제한했다.

• 현재 i를 뽑았다면 다음 재귀에서는 i+1부터만 고를 수 있게 함
• 그래서 자동으로 중복/역순이 발생하지 않는다

 

상세 아이디어

• picked : 현재까지 선택한 숫자들을 담는 벡터
• depth : 현재까지 몇 개를 뽑았는지(선택 개수)
• start : 다음에 뽑을 수 있는 최소 숫자

동작 흐름은 다음과 같다.

1. 종료 조건
   depth == m이면 M개를 모두 뽑은 상태이므로 picked를 출력하고 종료한다.
2. 재귀 탐색
   i = start부터 n까지 돌면서:

• picked.push_back(i)로 선택
• backTracking(i + 1, depth + 1)로 다음 숫자는 더 큰 수만 선택하도록 재귀
• 재귀가 끝나면 picked.pop_back()으로 선택을 되돌림(백트래킹)

이 방식으로 모든 조합을 빠짐없이 탐색하면서도, 출력은 항상 오름차순이 된다.

 

구현 시 주의할 점

• 조합 문제에서는 start를 이용해 다음 선택 범위를 제한해야 중복 순열이 나오지 않는다.
• 재귀 호출 후에는 반드시 pop_back()으로 이전 상태로 되돌려야 한다.
  (안 하면 선택 값이 누적되어 출력이 깨짐)
• depth는 “현재까지 뽑은 개수”이므로, 시작은 0으로 두는 것이 자연스럽다.

 

---

 

코드

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

int n, m;
vector<int> picked;

void backTracking(int start, int depth)
{
	if (depth == m)
	{
		for (int i = 0; i < picked.size(); i++)
			cout << picked[i] << ' ';
		cout << '\n';

		return;
	}
	for (int i = start; i <= n; i++)
	{
		picked.push_back(i);
		backTracking(i + 1, depth + 1);
		picked.pop_back();
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	backTracking(1, 0);

	return 0;
}