[알고리즘] 중복조합

중복조합

• 서로다른 n개의 원소 중, 중복을 허락하여 r개를 뽑는 것.
• nHr = (n+r-1)C(r)
• 조합에서의 중복만 허용하므로 순서는 여전히 상관하지 않는다.(조합)
• dfs에서 i+1이 넘어가면 조합, i가 넘어가면 중복조합

def dfs(idx, depth):
    if depth == r:
        print(*comb)
    for i in range(idx,n):
        comb[depth] = arr[i]
        dfs(i, depth + 1)

• n-1개의 칸막이를 뽑아야하는 요소들 r개 사이에 배치하는 경우의 수.
• = n-1개의 막대기로 구분된 영역에 요소를 집어넣는 경의의 수.
• nHr = n-1+r C n-1 = n-1+r C r

다음에 예제 풀어 첨부할 것.