[백준][20단계 백트래킹] 15652번 /N과 M (4) (파이썬/Python)

1. 문제 설명

2. 코드

import sys

input = sys.stdin.readline
N,M = map(int,input().split())

path = []
out = []

def dfs(start):
    if len(path) == M:
        out.append(" ".join(map(str,path)))
        return
    for x in range(start,N+1):
        path.append(x)
        dfs(x)
        path.pop()
dfs(1)
sys.stdout.write("\n".join(out))

3. 풀이 과정

N과 M (2)에 포인트가 하나만 추가된 문제이다.

https://litd.tistory.com/666

[백준][20단계 백트래킹] 15650번 /N과 M (2) (파이썬/Python)

같은 수를 여러 번 골라도 되고, 비내림차순으로 해야 된다.

시작점을 for문의 x로 하면 문제가 해결된다.

4. 자투리 개념

• 백트래킹 알고리즘
  - 정답을 구성해 가는 중간 단계들을 체계적으로 탐색하되, 불필요한 가지는 일찍 잘라내는(Pruning) 깊이우선탐색(DFS)

핵심 아이디어

• 문제의 해 공간(Search Space):
  가능한 모든 해(또는 부분해)를 트리 형태로 생각합니다. 루트는 “아무 것도 선택하지 않음”, 깊이 d는 “d개 선택 완료”.
• 부분해(Partial Solution):
  아직 완성은 아니지만 제약을 만족하며 확장될 수 있는 중간 상태.
• DFS + 되돌리기(Backtrack):
  하나를 선택(choose) → 더 내려가서 탐색(explore) → 돌아오며 선택을 취소(unchoose)합니다.
• 가지치기(Pruning):
  제약을 위반하거나, 더 진행해도 정답이 절대 나오지 않을 “가지”는 즉시 탐색을 멈춥니다.

공통 템플릿

def backtrack(state):
    if 완성조건(state):
        정답 처리
        return

    for candidate in 후보집합(state):  # 보통 정렬/오름차순으로 순회
        if 제약을 만족(candidate, state):  # 가지치기 1차
            state에 candidate를 반영(choose)
            backtrack(state)
            state에서 candidate를 되돌리기(unchoose)  # 핵심