[알고리즘] 백트래킹

• 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

---

📕 문제 1. N과 M (1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열

- 해결 아이디어

비어있는 리스트에서 시작해 수를 하나씩 추가하면서 길이가 M인 수열이 완성되면 출력

 

- e.g. N: 4, M: 2 == 1부터 4까지 자연수 중 중복없이 2개를 고른 수열

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
answer = [0] * M
visited = [False] * (N+1)


def backtrack(k):  # k번째 인덱스에 값을 넣는 함수
    if k == M:
        print(*answer)
        return
    for i in range(1, N+1):
        if not visited[i]:
            answer[k] = i
            visited[i] = True
            backtrack(k+1)
            visited[i] = False


backtrack(0)

---

💻 연습 문제

바킹독 - 백트래킹 문제집

---

ℹ️ 참고

바킹독 - 백트래킹