조합 구하기

재귀를 이용한 조합 구하기

 

dfs처럼 방문 체크를 해주면서 k개가 될때까지 계속 재귀를 돌기

#include <iostream>
#include <vector>


using namespace std;
int n = 5, k = 3, a[5] = {1, 2, 3, 4, 5};
void print(vector<int> b)
{
    for (int i : b)
        cout << i << " ";
    cout << '\n';
}
void combi(int start, vector<int> &b)
{
    if (b.size() == k)
    {
        print(b);
        return;
    }
    for (int i = start + 1; i < n; i++)
    {
        b.push_back(i);
        combi(i, b);
        b.pop_back();
    }
    return;
}
int main()
{
    vector<int> b;
    combi(-1, b);
    return 0;
}

 

-- 반복문을 이용해서 구하기

n이 2개면 2중, 3개면 3중 for문..

n이 많아질수록 비효율적이된다