728x90
조합.
depth를 증가 시키는 것과, start를 하나 더 늘리는 것이 관건이다.
한 재귀함수가 호출되면, depth가 고정되어 있는 채로, start와 관련된 i 인덱스가 바뀌면서 다음 조합의 수를 채운다.
#include <cstdio>
int N, M;
int a[9];
void combination(int depth, int start){
if (depth == M){
for (int i=0; i<M; ++i) printf("%d ", a[i]);
puts("");
return;
}
for (int i=start; i<=N; ++i){
a[depth] = i;
combination(depth + 1, i + 1);
}
}
int main() {
scanf("%d %d", &N, &M);
combination(0, 1);
return 0;
}
또는 stack (vector)을 이용해서 하는 방법이 있다.
stack이 M개 만큼 꽉차면 출력한다.
#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> vi;
int n, m;
void printlnVector(vi & v){
for (int i=0; i<v.size(); ++i) printf("%d ", v[i]);
printf("\n");
}
void dfs(vi & v){
if (v.size() == m){
printlnVector(v);
return;
}
int smallest = v.empty() ? 0 : v.back();
for (int i=smallest + 1; i<=n; ++i){
v.emplace_back(i);
dfs(v);
v.pop_back();
}
}
int main() {
scanf("%d %d", &n, &m);
vi vec;
dfs(vec);
return 0;
}
728x90
'알고리즘, 자료구조 > 알고리즘' 카테고리의 다른 글
[백준] 15651 N과 M (4) - 중복조합 (0) | 2019.09.19 |
---|---|
[백준] 15651 N과 M (3) - 중복순열 (0) | 2019.09.19 |
[백준] 15649 N과 M (1) - 순열 (2) | 2019.09.19 |
[BFS] 2206 벽 부수고 이동하기 (0) | 2019.09.12 |
[백준] 1694 숨바꼭질 (0) | 2019.09.12 |
댓글