알고리즘 /Backtracking
[백준] N과 M (2)_15650 (조합)
장주아
2019. 8. 9. 03:28
4 3
1 2 3
1 2 4
1 3 4
2 3 4
중복없이, 오름차순으로 출력해야 된다는 말은 조합의 개념이다. 순열처럼 숫자들의 순서가 다르다고 해서 다른 수열이 되는 것이 아니다. 어떤 숫자들을 뽑았을때 그것이 이루는 순서는 오름차순대로 단 하나밖에 없다.
순열과 전체적으로 비슷하지만, 오름차순대로 출력하기 위해 idx라는 변수가 하나 더 생겼다. 1 3 2 같은 조합은 있을 수 없다. dfs를 시작할때마다 숫자를 뽑을때, idx 다음부터 뽑는다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <iostream>
using namespace std;
int N, M;
bool select[8];
void printCombination() {
for (int i = 0; i < N; i++) {
if (select[i]) cout << i + 1 << " ";
}
cout << "\n";
}
void dfs(int cnt, int idx) {
if (M == cnt) {
printCombination();
return;
}
for (int i = idx; i < N; i++) {
if (select[i]) continue;
select[i] = true;
dfs(cnt+1,i);
select[i] = false;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> N >> M;
dfs(0, 0);
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |