[인프런] 조합 구하기

문제

• 1~N까지의 구슬이 있을 때, M개를 뽑는 방법의 수를 출력
• n: 구슬의 갯수 (3 <= N <= 10)
• m: 몇개를 뽑을지 (2 <= M <= N)
• 출력 순서는 사전순으로 오름차순으로 출력할 것

생각

• DFS를 사용하여 재귀적으로 풀자

Solution

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


def dfs(level, start):
    global cnt
    if level == m:
        for j in range(level):
            print(res[j], end=" ")
        cnt += 1
        print()
    else:
        for i in range(start, n + 1):
            res[level] = i
            dfs(level + 1, i + 1)


dfs(0, 1)
print(cnt)