[백준 15650 N과 M (2) 문제] PYTHON

지난 N과 M 문제와 거의 동일한 문제였지만 백트래킹 문제라는 것을 뒤늦게 알게되어 시도해봤다.

백트래킹은 처음 시도해봐서 N과 M(1) 문제 풀이를 보며 2를 풀어봤다.

백트래킹은 DFS와 비교해서 비슷한 개념이지만 DFS는 완전 탐색인 것에 비해

백트래킹은 탐색을 하는 도중 유망하지 않은 인자의 자식 노드를 탐색하지 않는다.

A, B = map(int, input().split())
visit = [False]*A
result = []


def backtracking(depth, A, B):
    if depth == B and result == sorted(result):
        print(' '.join(map(str, result)))
        return
    for i in range(A):
        if not visit[i]:
            visit[i] = True
            result.append(i+1)
            backtracking(depth+1, A, B)
            visit[i] = False
            result.pop()


backtracking(0, A, B)