[백준,Python]15649번 N과 M (1)(Backtracking)

이런 유형의 탐색 문제를 만났을 때,

가장 먼저 모든 경우의 수를 다 계산해야 풀 수 있는 가를 생각해본다.

그렇지 않다면 함수로 조건문을 사용하여 빠르게 탐색않해도 될 부부을 정의할 수 있는 방안이 무엇인지 생각한다.
예를 들어, 이 문제에서는 중복된 수열에 대해서는 탐색하지 않아도 된다. 
실제로 수열의 크기가 커진다면 굉장히 Critical 해질 수 있는 부분이다. ( 1 1 2 3 4 5 6 7 8 ...) 또한 사전 순으로 증가하는 순서로 출력하는 부분에서 탐색 범위가 한정되었다. 

Brute Force 로 접근할 경우,수열의 크기가 커질 경우,  가능한 모든 조합을 찾고 그 중에서 필터링하는 방법은 시간이 굉장히 오래 걸리고 비효율적이다. 

따라서 처음 빈 수열을 입력 받아 , 조건이 맞을 때 출력을 하며 조건이 맞을 경우 재귀함수를 돌려 가능한 수을 탐색하도록 하는 Backtracking 함수를 아래와 같이 구현하였다. 

import sys
input = sys.stdin.readline

N,M = map(int, input().split())

def backtrack(s):
    # 만족하는 길이에 도달
    if len(s) == M:
        print(' '.join(map(str,s)))
        return

    # 재귀식 탐색
    for i in range(1,N+1):
        if i not in s:
            s.append(i)
            backtrack(s)
            s.pop()

backtrack([])