Backtracking 구현 (Python)

백트래킹과 DFS의 차이

• 백트래킹은 불필요한 탐색을 하지 않음
  ex) 132, 234, 123 중에서 123을 찾고자 할 때,
  132에 접근 시 십의 자릿수가 다르면 더 이상 탐색을 하지 않고 다음 수로 넘어감

구현

• 자연수 N, M이 주어질 때, 숫자 1부터 N까지 중복 없는 M개의 요소를 가진 수열을 구하는 문제
  
• 재귀의 탈출 조건 -> 배열의 길이가 M에 도달 했을 때 출력하고 return
• 배열의 길이가 M이 넘는 지 확인하고 -> 1) 넘는다면 출력 & return, 2) 넘지 않는다면 배열을 순서대로 채움

N, M = map(int, input().split())
ans = []

def backtracking():
    if len(ans) == M:
        print(" ".join(map(str, ans)))
        return
    for i in range(1, N+1):
        if i not in ans:
            ans.append(i)
            backtracking()
            ans.pop()

backtracking()