[순열과 조합] 중복조합

중복조합(combination with repitition) : 서로 다른 n개의 원소 중, 중복을 허락하여 r개를 뽑는 것

기호 H로 표시

핵심

1. 1,2,3,4,5중 2개를 뽑는 중복조합의 수는 2+(5-1)C2=15개

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

3. 중복조합은 조합에서 중복만 허용한 것이므로 똑같이 수의 순서는상관X

ex) (1,2)와 (2,1)는 같음

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

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

특징: 조합에서 중복만 허용하므로 조합 코드와 거의 똑같다.

(dfs함수내부에서, 재귀를 타고 넘어가는 dfs함수의 첫번째 인자가 i+1일 때 조합, i일때 중복조합)

코드

#include<iostream>
using namespace std;
int arr[5] = { 1,2,3,4,5 };
int combi[5];
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 < 5; i++)
    {
        combi[cnt] = arr[i];
        dfs(i, cnt + 1);
    }
}
int main()
{
    dfs(0,0);
}

결과

5H2=15개