[백준 C++] 15650 N과 M (2) - 백트래킹

15650번: N과 M (2)

#include <iostream>
using namespace std;

int N, M;

void DFS(int Sequence[], int Index, int Number)
{
	if (Index == M)
	{
		for (int i = 0; i < M; ++i)
		{
			cout << Sequence[i] << ' ';
		}
		cout << '\n';
		return;
	}

	Sequence[Index] = Number;
	if (Number <= N)
	{
		DFS(Sequence, Index + 1, Number + 1);
		DFS(Sequence, Index, Number + 1);
	}
}

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

	cin >> N >> M;

	int Sequence[8];
	DFS(Sequence, 0, 1);
}

---

 

DFS & 백트래킹을 이용해서 푸는 문제입니다.

1부터 N까지 각 숫자를 고를 때와 안 고를 때를 DFS로 탐색하도록 하고,

현재 숫자가 N을 넘어가면 더 깊이 들어가지 않도록 해서 풀었습니다.