[순열과 조합] 조합

조합(combination) : 서로 다른 n개의 원소 중, 순서에 상관없이 r개를 선택 하는 것

기호 C로 표시

핵심

1. 1,2,3,4 중 2개를 뽑는 조합은 4C2= 4*3*2*1 / 2*1 = 12개

2. 정의에 따라 (1,1), (2,2), (3,3), (4,4)는 포함X

3. 조합은 수의 순서가 상관없으므로 (1,2)와 (2,1)는 같음

*순열: 순서가 상관 있으므로 (1,2)와 (2,1)는 다름

4. 백트래킹 기법을 사용하여 구현한다.

(순열코드처럼 명시적으로 백트래킹기법을 사용하진않았지만, 가지치기를하며 진행되므로 같음)

구현: 1,2,3,4중 2개를 뽑는 조합

코드

#include<iostream>
using namespace std;
int arr[4] = { 1,2,3,4};
int combi[4];
void dfs(int index,int cnt)
{
    if (cnt == 2)
    {
        for (int i = 0; i < 2; i++)
        {
            cout << combi[i] << " ";
        }cout << endl;
        return;
    }
    for (int i = index; i < 4; i++)
    {
        combi[cnt] = arr[i];
        dfs(i+1, cnt + 1);
    }
}
int main()
{
    dfs(0,0);
}

결과

4C2=6개