[Python Algorithm] 완전탐색(DFS) - 조합 구하기

> 완전탐색 - 백트랙킹, 상태트리와 CUT EDGE / 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

def DFS(L, s):
    global cnt
    if L == m:
    	for x in res:
        	print(x, end=' ')
        cnt+=1
        print()
    else:
    	for i in range(s, n+1):
        	res[L] = i
        	DFS(L+1, i+1)
           




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

 

 

 

 

⭐️ Point ! ⭐️

• 이 문제 다른 DFS문제에 기초로 많이 쓰임 ! , 가지 뻗는 방법과 출력 방법 응용하기

 

• 조합은 시작점이 있음 ! (s변수)

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이