백준 15649 : N과 M (1) with 파이썬

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

1) 순열 : 순서에 상관있게 m개 중 n개를 뽑는 경우

1. permutation

 

2. 백트래킹 : 재귀함수 (힌트 : 시간복잡도 계산시 N이 작아 8~10이하)

ⓐ사용하는 상황 : 모든 경우의 수를 확인해야 하지만, for문으로 확인 불가능한 경우 (깊이=선택갯수가 달라질 때)

ⓑ작동방법 : 트리구조를 재귀함수로 탐색

ⓒ시간복잡도(<=10^8)

- 증복가능 : O(N^N)으로 N=8까지 가능

- 중복불가능 : O(N!)으로 N=10까지 가능

 

 

import sys
input=sys.stdin.readline
n,m=map(int, input().split())
chk=[False]*(n+1)
rs=[]

def recur(num):
    if num == m :
        print(' '.join(map(str, rs)))   #join을 위해 str으로 변경
        return
    
    for i in range(1, n+1):
        if chk[i]==False :
            chk[i]=True
            rs.append(i)
            recur(num+1)   #재귀함수가 종료되면, 다시 위로 올라가 탐색해야 하므로
            chk[i]=False   #위의 방문처리를 취소하고, 이전에 넣었던 것을 꺼내야
            rs.pop()
            
recur(0)