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

 

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

 

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

15650번: N과 M (2)

---

 

해결전략

 

조합 Combination, 백트랙킹 Backtracking

---

 

정답 코드

 

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

int n, m;
int arr[9], ch[9]; // arr는 선택된 수를 저장하는 배열, ch는 해당 수가 선택되었는지를 확인하는 체크 배열

void DFS(int idx, int cnt) // idx는 현재 탐색을 시작할 위치, cnt는 현재까지 선택된 숫자의 개수
{
	if (cnt == m) // m개의 숫자가 모두 선택되었다면 해당 수열을 출력
	{
		for (int i = 0; i < m; i++) {
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = idx; i <= n; i++) // idx부터 n까지의 수에 대해 탐색
	{
		if (ch[i] == 0) // 만약 i가 아직 선택되지 않았다면
		{
			ch[i] = 1; 				// i를 선택
			arr[cnt] = i;			// arr의 cnt 위치에 i를 저장
			DFS(i + 1, cnt + 1);	// 다음 숫자를 선택하기 위해 DFS 함수를 재귀 호출
			ch[i] = 0;				// 재귀 호출이 끝나면 i의 선택을 취소. 이는 다른 수열을 생성하기 위한 백트래킹
		}
	}
}

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

	cin >> n >> m;

	DFS(1, 0);

	return 0;
}

 

 

---