n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘

0~n-1까지 n개의 원소가 있을 때 그 중 m개를 고르는 모든 조합을 출력한다.

 

n: 전체 원소 수

picked: 지금까지 고른 원소들의 번호

toPick: 더 고를 원소의 수

 

#include <cstdio>
#include <vector>
using namespace std;

void printPicked(vector<int> picked)
{
    for(int i : picked)
        printf("%d ",i);
    printf("\n");
}

void pick(int n,vector<int>& picked,int toPick)
{
    if(toPick==0)
    {
        printPicked(picked);
        return;
    }
    
    int smallest=picked.empty()?0:picked.back()+1;
    for(int next=smallest;next<n;next++)
    {
        picked.push_back(next);
        pick(n,picked,toPick-1);
        picked.pop_back();
    }
}

int main()
{
    vector<int> picked;
    pick(10,picked,4);
    return 0;
}