[알고리즘] 백트래킹

모든 경우의 수를 확인해야할 때, for로는 확인 불가한 경우(깊이가 달라질 때)

순열: m 중에 n을 뽑을때 순서가 상관 있는 경우

 

 

# 아이디어

1부터 N중에 하나를 선택한뒤

다음 1부터 N까지 선택할 때 이미 선택한 값이 아닌 경우 선택

M개를 선택할 경우 프린트

 

# 시간 복잡도

중복가능) n^n (8까지 가능)

중복불가) n! (10까지 가능)

 

# 15649
'''
1. 아이디어
- 백트랙킹 재귀함수 안에서 for 돌면서 숫자 선택(이때 방문여부 확인)
- 재귀함수 M개를 선택할 경우 print

2. 시간 복잡도
- 중복불가 n!

3. 자료구조
- 결과값 저장 int[]
- 방문여부 체크 bool[]
'''
import sys
input = sys.stdin.readline

N, M=map(int,input().split())
result = []
check = [False]*(N+1)

def recur(num):
    if num == M:
        print(' '.join(map(str,result)))
        return
    for i in range(1,N+1):
        if check[i] == False:
            check[i] = True
            result.append(i)
            recur(num+1)
            check[i]=False
            result.pop()
recur(0)

 

 

https://youtu.be/atTzqxbt4DM?si=8RKzZJouQZKuta1P