(C++)조합

조합

순열과 다르게 순서는 상관없이 주어진 n개 중에서 r개을 뽑아서 나열하는 것

for문

최대 3개까지 뽑는경우에는 효율적이나 그 이상일 경우 재귀함수를 통해 구현하는 것이 효율적

#include<iostream>
#include<vector>

using namespace std;

vector<int> v;
int n = 5;

int main() {

    for (int i = 0; i < n; i++) {
        v.push_back(i + 1);
    }
    //5개중 3개를 뽑는 경우
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                cout << v[i] << ' ' << v[j] << ' ' << v[k] << '\n';
            }
        }
    }
    cout << '\n';

    //5개중 2개를 뽑는 경우
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            cout << v[i] << ' ' << v[j] << '\n';
        }
    }

    return 0;
}
//출력
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

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

재귀함수

재귀함수로 조합을 하는 경우에 탈출조건 : 뽑는 개수와 벡터안의 요소의 개수와 같을 때

처음에 combination(-1,v)로 시작하는 이유는 벡터가 뽑는 개수와 동일한 개수를 가졌을 때 pop_back()을 통해 마지막 요소를 버리고 이미 저장된 start값에서 +1을 한 요소부터 다시 저장하기 위해서이다. 만약 combination(0,v)로 한다면 start의 값이 배열 a에서 인덱스가 증가 하지 않기 때문에 중복된 값을 뽑아서 v에 저장하게 된다.
그러므로 -1부터 뽑은 요소의 인덱스를 임의로 증가시켜주기 위해서 -1로 설정후 for문에서 +1을 하는 방식을 사용한 것이다.

#include<iostream>
#include<vector>

using namespace std;

vector<int> a = { 2,3,4,5,6 };
int n = a.size();
int r = 3;

void combination(int start, vector<int> v) {
    if (v.size() == r) {
        for (auto ele : v) {
            cout << ele << ' ';
        }
        cout << '\n';
    }

    for (int i = start + 1; i < n; i++) {
        v.push_back(a[i]);
        combination(i, v);
        v.pop_back();
    }

}

int main() {
    vector<int> v;
    combination(-1, v);
    return 0;
}
//출력
2 3 4 
2 3 5 
2 3 6 
2 4 5 
2 4 6 
2 5 6 
3 4 5 
3 4 6 
3 5 6 
4 5 6