조합 - 완전 탐색

조합: 일부 원소를 선택해 부분집합을 만드는 방법

 

n명의 학생들이 주어졌을 때, c명의 학생을 선택해서 만들 수 있는 모든 경우의 수를 구하시오.

 

간단한 완전 탐색 문제이다. 몇명의 학생을 선택하는지 값이 고정되어 있다면, 선택해야 하는 숫자 개수 만큼 반복문을 순회하면 완전 탐색을 할 수 있다.

 

선택해야 하는 숫자 개수가 늘어나면 늘어날수록 코드를 보기 힘들기 때문에 아래는 재귀 함수형태로 구현한 코드이다.

완전 탐색 문제는 재귀 함수를 이용하면 간단하게 작성 할 수 있다.

 

void printPicked(vector<int>& picked)
{
	for(auto it : picked)
	{
		cout << it;
	}

	cout << endl;
}

void pick(int n, vector<int>& picked, int toPick)
{
	if(toPick == 0) { printPicked(picked); return;}

	int smallest = picked.empty() ? 0 : picked.back() + 1;	

	for(int next = smallest; next < n; ++next)
	{
		picked.push_back(next);
		pick(n, picked, toPick - 1);
		picked.pop_back();
	}

}

int main()
{
	// 첫번째는 총 학생 수, 두번째는 선택 수
	int n, c;
	scanf("%d %d", &n, &c);

	vector<int> students;
	vector<int> picked;

	for(int i = 0; i <n; ++i)	
	{
		students.push_back(i);
	}

	pick(n, picked, c);

	return 0;
}