[ 2023-02-26 👷‍♀️ TIL ]

백준 15649번

백트래킹 문제로 주어진 두 수에 n과 m에서 1~n까지의 m개의 수열을 중복없이 출력하는 문제입니다.

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
li = []

def back():
    global n, m, li

    if len(li) == m:
        print(' '.join(map(str, li)))
        return

    for i in range(1, n+1):
        if i not in li: # 가지치기
            li.append(i)
            back()
            li.pop()

back()

위에 문제는 백크래킹을 연습하는 문제입니다.

모든 경우의 수를 파악하는 알고리즘으로 DFS가 있는데 백트래킹은 DFS와 유사하지만
조건을 추가하여 불필요한 일을 수행하지 않도록 하는 알고리즘 방법입니다.