재귀를 이용한 조합

• n개의 요소 중에서 k개를 뽑는 경우 (순서 상관 없이)

#include<bits/stdc++.h>
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;
}

// 출력
0 1 2 
0 1 3 
0 1 4 
0 2 3 
0 2 4 
0 3 4 
1 2 3 
1 2 4 
1 3 4 
2 3 4

여기서 구하려는 대상은 a[5]라고 볼 수 있다.

출력되는 경우들은 인덱스로 표시한 것이므로, a[5] 배열에서 해당 인덱스의 요소를 가리킨다고 보면 된다.

요소가 중복되는 경우도 있을 수 있기 때문에 인덱스로 경우를 구하는 것이 덜 헷갈릴 것이다.

중첩 for 문을 이용한 조합

n개의 요소 중 k(=3)개를 뽑는 조합이라고 한다면 for문을 k 번 중첩하여 표현할 수 있다.

여기서 for 문 내의 i, j, k의 시작 값을 다르게 하거나 끝나는 값을 다르게 하는 이유는 순서와 중복 방지 때문이다!

간단한 예시로, 3개의 수 중 2개를 뽑는 상황이라고 할 경우,

만약 i 보다 j가 큰 값부터 for문을 돌도록 설정하지 않는다면,