문제 링크 -> https://www.acmicpc.net/problem/15649

접근

• 순열 문제이지만 백트래킹으로 풀었다.

코드

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
arr = []

def bt():
    if len(arr) == m:
        print(*arr)
        return
    
    for i in range(1, n+1):
        if i not in arr:
            arr.append(i)
            bt()
            arr.pop()

bt()

추가

백트래킹은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는 데 적합하다.
해를 구하는 도중 해가 아니어서 이전으로 돌아가 해를 찾는 기법이다.
DFS는 전체 검색이지만 백트래킹은 아닐 때는 중간에 나와서 전체 검색이 아니다. (가지치기)

def 재귀함수(x):
	if 정답:
    	출력
    else:
    	for 뻗을 수 있는 모든 자식 노드:
        	if 정답에 유망:
            	자식 노드로 이동
                재귀함수(x+1)
                부모 노드로 이동

유사 문제

N과 M (2) https://www.acmicpc.net/problem/15650
N과 M (3) https://www.acmicpc.net/problem/15651
N과 M (4) https://www.acmicpc.net/problem/15652
N-Queen https://www.acmicpc.net/problem/9663

참고
https://jie0025.tistory.com/455
https://jamesu.dev/posts/2020/04/13/baekjoon-problem-solving-15649/