[BaekJoon] 백준 알고리즘 15649번 / N과 M(1)/ 백트래킹 / Python

 

"""
1. 아이디어
- 백트래킹 재귀함수 안에서, for문 돌면서 숫자 선택( 단, 방문여부 확인할 것 )
- 재귀함에서 M개를 선택할 경우 해당 조합 print

2. 시간복잡도
- 해당 문제는 중복없는 순열을 출력이므로, N이 10까지 가능
- 따라서 N! 가능.

3. 자료구조
- 조합 저장 int[]
- 방문여부 체크 bool[]

"""

import sys
input = sys.stdin.readline

# 자연수 2개를 입력받는다.
N, M = map(int, input().split())

# 자연수의 조합을 저장하는 리스트 
rs = []
# 방문여부 체크를 저장하는 리스트
chk = [False] * (N+1)

def recur( num ):
    # 전달받은 파라미터가 조합의 갯수라면 print 후 출력
    if num == M:
        print( ' '.join( map( str, rs) ) )
        return
    # 입력받은 자연수 N개 크기만큼 for문 
    for i in range( 1, N + 1 ):
        if chk[i] == False:
            # 방문 체크
            chk[i] = True
            # 리스트에 추가
            rs.append( i )
            # 대기중... 재귀함수 호출( 호출.. 호출.. M까지 반복 후 num이 M과 같다면 해당 함수 종료 후 돌아옴. )
            recur( num + 1)
            # 현재 위치로 돌아왔다면 1 => 2로 가기위해서 조합 리스트, 방문여부 리스트 초기화
            chk[i] = False
            rs.pop()



# 초기, 함수 호출
# 인자값은 조합된 수량을 의미
recur(0)