[Algorithm] 조합 (Combination)

조합

어떤 리스트에서 N개를 중복 없이, 순서를 고려하지 않고 선택하는 것을 말한다.

예를들어 {1,2,3}에서 2개를 선택하는 경우

{1,2}
{1,3}
{2,3}

총 3가지 경우의 수가 존재한다.

 

조합 형태

int selectCount = 2; // 선택할 개수

void  combi(int start, vector<int> v)
{
   if (v.size() == selectCount)
   {
     // Logic
     return;
   }
   for (int idx = start + 1; idx < selectCount; idx++)
   {
     v.push_back(idx);
     Combination(idx, v);
     v.pop_back(idx);
   }
}

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

• combi 함수는 재귀 함수이다.
  • 기저 사례를 충족할 때까지(size == 2) 빈 벡터에 인덱스를 순차적으로 집어 넣는다.
  • 기저 사례를 충족하면 함수 호출을 종료하고 이전 단계로 돌아간다.
  • DFS와 동일한 방식으로 동작한다.

 

조합의 개수

• nCr =  n개 중 r개를 선택할 수 있는 경우의 수 (중복이 없으며, 순서에 상관없이)
• n = 총 개수
• r = 선택할 개수

 

참고

[수학] 순열, 조합 공식 총정리