[C++] 조합

조합은 순서를 고려하지 않습니다.

순서는 고려하지 않고 다양하게 몇 개를 뽑을 지에 집중합니다.

 

출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=vollollov&logNo=220915481071

 

조합을 구현하는 테크닉은 3가지가 있습니다.

 

중첩 반복문

n명 중 r개를 선택하는 방법일 때, r의 수가 3개 이하라면 반복문으로 빠르고 쉽게 구현할 수 있습니다.

for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
    		for (int k = j + 1; k < n; k++) {
            	}
    	}
}

next_permutation 을 이용하자.

순열의 특징을 가져와 1은 애들이 선택됐다고 보면 되고, 0은 선택받지 못한 애들이 됩니다.

즉 5C2 라면 chk 배열을 {0, 0, 0, 1, 1}이라고 두고, 1일 때에만 출력하면 됩니다.

int main()
{
	vector<int> input = { 3,5,1,7,9 };
	vector<int> chk = { 0,0,0,1,1 };
	do
	{
		for (int i = 0; i < chk.size(); i++)
		{
			if (chk[i] == 1)
			{
				cout << input[i] << ' ';
			}
		}
		cout << '\n';
	} while (next_permutation(chk.begin(), chk.end()));
}

7 9
1 9
1 7
5 9
5 7
5 1
3 9
3 7
3 1
3 5

재귀 구현

조합이라는 것도 즉, 그 현재 순간에 내가 하나를 선택하는 방법입니다.

따라서 그 순간 마다 하나를 pick 하는 과정이 동일하기 때문에 재귀 방법으로 구현할 수 있습니다.

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

// 5C2 구하기 (조합)
int n = 5, k = 2;
vector<int> v = { 3,5,1,7,9 };

void combi(int start, vector<int>& picked)
{
	if (picked.size() == k)
	{
		for (int it : picked) cout << it << ' ';
		cout << '\n';
		return;
	}

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

int main()
{
	vector<int> picked;
	combi(-1, picked);
}

재귀 방법이 처음에는 이상한 구조라고 생각되지만, 쉽게 현재 구간에서 나는 어떤 선택을 할 것인지를 결정해 주면 됩니다.

동시에 기저사례(종료조건)은 nCr 일 때 이미 r개를 뽑았다면 그때를 출력하고 빠져나가면 됩니다.