[인프런] 조합 구하기

---

문제설명

1부터 N까지 번호가 적힌 구슬이 있다. 이 중 M개를 뽑는 방법의 수를 출력해라.

입력조건

• 첫 줄에 자연수 N(3 <= N <= 10)과 M(2 <= M <= N)이 주어진다.

출력조건

• 첫 줄에 결과를 출력한다. 맨 마지막 총 경우의 수를 출력한다.
• 출력순서는 사전순으로 오름차순으로 출력한다.

사고과정

• 조합을 구하는 경우는 순열을 구할 때 상태트리랑 다르게 만들어야 한다. 
• 즉 for loop 문에서 구현하는 방법이 다르다.

풀이

n, m = map(int, input().split())
res = [0] * m
cnt = 0

def dfs(L, S):
    global cnt
    # 종단
    if L == m:
        for r in res:
            print(r, end=' ')
        print()
        cnt += 1
        return
    else:
        for i in range(S, n+1):
            res[L] = i
            dfs(L+1, i+1)

dfs(L=0, S=1)  # L은 res의 인덱스(레벨), S는 가지 위의 값!
print(cnt)