[알고리즘] 백트래킹

백트래킹이란?

- 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하는 방법 - 원하는 값이 아닐 경우 더 이상 탐색을 진행하지 않고 전 단계로 back 해서 돌아가는 방법 -> 이름 그대로 backtracking

백트래킹 vs DFS

- 두 알고리즘 모두 탐색 알고리즘 - 백트래킹 문제는 dfs로, dfs 문제는 백트래킹으로 문제 해결 가능 - dfs는 원하지 않는 경우더라도 트리의 바닥까지 모든 경우의 수를 탐색하지만, 백트래킹 알고리즘은 불필요한 탐색 x

---

N과 M

• 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 프로그램
• 수열은 사전 순으로 증가하는 순서로 출력

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


def back():
    # 원하는 길이의 순열이 완성되면 출력
    if len(answer) == M:
        print(" ".join(map(str, answer)))
        return

    # i는 1부터 N까지의 숫자
    for i in range(1, N + 1):
        # 순열이므로 겹치는지 아닌지 확인
        # 중복이 아니면 숫자 i를 리스트에 추가
        if i not in answer:
            answer.append(i)
            back()
            # return 되서 돌아오면 전 단계로 돌아감
            # 예를 들어 순열이 1,2,3이면 return 되서 돌아온 후 3이 pop되고
            # 1,2에서 다음 값을 찾는 형식으로 전 단계로 돌아가는 것
            answer.pop()


back()