[DFS기초] - 조합

조합

1부터N까지번호가적힌구슬이있습니다.이중 M개를뽑는방법의수를출력하는프로그 램을 작성하세요.

 

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

▣ 출력설명
첫 번째 줄에 결과를 출력합니다.

맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.

 

▣ 입력예제 1

4 2

▣ 출력예제 1

1 2
1 3
1 4

2 3

2 4

3 4

6

 

 

나의 코드

 

흠....구현하지 못했다..

체크 배열로 이것저것 생각해 보았지만..실패..

 

정답코드

import sys
sys.stdin=open("input.txt", "r")
def DFS(L, s):
    global cnt
    if L==m:
        for i in range(m):
            print(res[i], end=' ')
        print()
        cnt+=1
    else:
        for i in range(s, n+1):
            res[L]=i
            DFS(L+1, i+1)
           

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

조합은 순열처럼 체크 배열로 푸는게 아닌 순회하는 인덱스를 인자로 넣어 제어한다 !!