[무식하게 풀기 - 재귀] N개의 원소중 M개를 고르는 모든 조합 찾는 방법

골라야 할 원소의 수(M)가 입력에 따라 달라지는 경우 반복문 보다 재귀를 사용하면 유연하게 대처할 수 있다.

 

0부터 N-1까지의 수중에 M개를 고르는 모든 경우의 수를 구하는 코드

 
#include <iostream>
#include <vector>
using namespace std;
int maxN, maxM;
 
void printNumber(vector<int>& picked) {
    int cnt = picked.size();
    for(int i=0; i<cnt; i++) {
        cout<<picked[i]<< ',';
    }
    cout<<endl;
}
 
void recursive(vector<int>& picked) {
    if(picked.size() == maxM) { // M개를 골랐으면 출력한다.
        printNumber(picked);
        return;
    }
    
    int biggestNum = 0;
    if(!picked.empty())
        biggestNum = picked.back()+1; //지금까지 고른수중 가장큰수의 다음 수부터 후보로 선정한다.
    
    for(int i=biggestNum; i<maxN; i++) {
        picked.push_back(i); //i를 넣어보고
        recursive(picked); //경우의 수를 만든 뒤
        picked.pop_back(); //i를 제거한다.
    }
}
 
int main(int argc, const char * argv[]) {
    vector<int> vt;
    scanf("%d %d", &maxN, &maxM);
    recursive(vt);
    return 0;
}
 

 

[실행 결과]

6 3

0,1,2,

0,1,3,

0,1,4,

0,1,5,

0,2,3,

0,2,4,

0,2,5,

0,3,4,

0,3,5,

0,4,5,

1,2,3,

1,2,4,

1,2,5,

1,3,4,

1,3,5,

1,4,5,

2,3,4,

2,3,5,

2,4,5,

3,4,5,