N과 M (2) ( 15650 번 )

15650번: N과 M (2)

 

---

🧠 알고리즘

• 백트래킹 (Backtracking)

 

✔️ 동작 방식

• 문제 핵심 아이디어
  • 1부터 N까지의 자연수 중에서 중복 없이 M개를 선택하는 모든 조합을 구하는 문제이다.
  • 현재 선택된 수열(now_lst)과 시작 인덱스(start)를 기준으로 재귀적으로 탐색한다.
• 재귀 구조
  1. 현재 수열(now_lst)의 길이가 M이면 출력하고 재귀 종료.
  2. 아직 길이가 M보다 짧다면, 시작 인덱스 start부터 N까지 반복:
     • n_lst[idx]를 수열에 추가
     • _dfs(idx + 1, now_lst) 재귀 호출 (다음 수부터 선택)
     • 재귀 종료 후 pop()으로 수열 상태 복원 (백트래킹)
• 최종 출력
  • 길이가 M인 모든 조합을 탐색 과정에서 즉시 출력한다.

---

 

🧾 코드

import sys
# 필요한 파라미터
# 1) 현재 위치
# 2) 현재 배열

def _dfs(start, now_lst):
    if len(now_lst) == m:
        print(*now_lst)
        return

    for idx in range(start, n):
        num = n_lst[idx]
        now_lst.append(num)

        _dfs(idx + 1, now_lst)

        now_lst.pop()
    

n, m = map(int, sys.stdin.readline().rstrip().split())
n_lst = [i for i in range(1, n + 1)]

_dfs(0, [])

---

 

⏱️ 시간 복잡도

_dfs(now_lst) : 백 트래킹 ( 팩토리얼 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 팩토리얼 시간 복잡도 ( O(N! / (N−M)!) )