1 <= M <= N <= 8 조건의 중복 없이 M개를 고른 수열을 고르세요. 단 수열은 오름차순입니다.
m C n인 조합의 경우의 수를 구하는 문제입니다.
🔔 Kick Point :
순열을 구하는 방법이랑 비슷하게 구하는 문제였습니다. 대신 여기선 조건을 추가를 해야했는데요
dfs 함수에 num 이라는 변수를 두어, for 루프를 돌려서 수를 찾을 때 이전 자리수 크기보다 무조건 크게 만들어야합니다.
예를 들어 N = 4, M = 3 인 경우에서 경우의 수를 찾아보면,
1 2 3
1 2 4
1 3 4
2 3 4
첫번째 자리수 arr[0] < 두번째 자리수 arr[1] < 세번째 자리수 arr[2] 조건을 만족하기 때문입니다.
🔔 Code :
#include <iostream>
#define MAX 9
using namespace std;
int n, m;
int arr[MAX] = { 0, };
bool visited[MAX] = { 0, };
void dfs(int num = 1, int cnt = 0) {
if (cnt == m) {
for (int i = 0; i < m; i++)
cout << arr[i] << ' ';
cout << '\n';
return;
} // 정답일때
for (int i = num; i <= n; i++) {
if (!visited[i]) {
visited[i] = true;
arr[cnt] = i;
dfs(i + 1, cnt + 1);
visited[i] = false;
}
}
}
int main() {
cin >> n >> m;
dfs(1, 0);
}