15649_N과 M(1)

문제 링크

백트래킹의 핵심은 가지치기

• 첫번째 풀이
  visited 리스트를 활용하여 각 숫자 방문 표시
  함수 인자를 1씩 증가시켜서 m개가 됐을때 모두 출력후 한 단계 빠져나옴
  빠져나온뒤 방문 false 처리

n, m = map(int, input().split())
visited = [0] * (n+1)

arr = [0] * m
def backtracking(k):
    if k == m:
        print(*arr)
        return
    
    for i in range(1, n+1):
        if not visited[i]:
            arr[k] = i
            visited[i] = 1
            backtracking(k+1)
            visited[i] = 0
backtracking(0)

• 두번째 풀이
  visited 없이 풀기
  리스트에 i를 넣어주고 다음 회차때 해당 i continue

n, m = map(int, input().split())

s = []

def backtracking():
    if len(s) == m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(1, n+1):
        if i in s: 
            continue
        s.append(i)
        backtracking()
        s.pop()

backtracking()