[백준] N과 M (2)_15650 (조합)

4 3
1 2 3
1 2 4
1 3 4
2 3 4

 

중복없이, 오름차순으로 출력해야 된다는 말은 조합의 개념이다. 순열처럼 숫자들의 순서가 다르다고 해서 다른 수열이 되는 것이 아니다. 어떤 숫자들을 뽑았을때 그것이 이루는 순서는 오름차순대로 단 하나밖에 없다.

 

순열과 전체적으로 비슷하지만, 오름차순대로 출력하기 위해 idx라는 변수가 하나 더 생겼다. 1 3 2 같은 조합은 있을 수 없다. dfs를 시작할때마다 숫자를 뽑을때, idx 다음부터 뽑는다.

 

#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;
}