[알고리즘] 조합(Combination)

조합

1. next_permutation을 활용한 조합 생성

방법 설명

• 주어진 배열을 정렬한 후, 특정 개수만큼의 1과 0으로 비트마스크를 만든 다음, 이 마스크를 통해 가능한 모든 조합을 생성하는 방식입니다.

• 예를 들어, 5C3 조합을 구하려면 [0, 0, 0, 1, 1]과 같은 배열을 만들고, next_permutation을 통해 배열의 모든 순열을 탐색합니다. 이때 1이 위치한 인덱스의 요소들을 조합으로 선택합니다.

구현 예시

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main()
{
    vector<int> arr = { 1, 2, 3, 4, 5 }; //5C3
    vector<int> bin = { 0, 0, 0, 1, 1 };
    do {
        int index = 0;
        for (auto i : bin) {
            if (i == 0) {
                cout << arr[index] << ' ';
            }
            index++;
        }
        cout << "\n";
    } while (next_permutation(bin.begin(), bin.end()));
    return 0;
}

2. 재귀를 사용한 조합 생성

방법 설명

• 조합을 생성할 때마다 직접적으로 배열에서 필요한 요소만 선택해 나가는 방식입니다.

• 현재 위치에서 다음 요소를 선택할지 말지를 결정하면서 모든 조합을 탐색합니다.

구현 예시

void Collaboration(vector<int>& target, vector<int>& selected, int depth, int next, int r) {
	if (depth == r) {
		PrintArray(selected);
		return;
	}

	for (int i = next; i < target.size(); ++i) {
		selected.push_back(target[i]);
		Collaboration(target, selected, depth + 1, i + 1, r);
		selected.pop_back();
	}
}