15649번: N과 M(1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 백트래킹 문제: DFS로 풀어보기

아이디어

• n = 4, m = 2 인 경우
  • 1 ⇒ (2, 3, 4)
  • 2 ⇒ (1, 3, 4)
  • 3 ⇒ (1, 2, 4)
  • 4 ⇒ (1, 2, 3)

1. 먼저 i를 넣어주고, 다음 수들이 없다면 넣어주고
   1. 넣은 리스트의 길이가 M이면 리스트 출력 후 돌아가기
      1. 아니면 또 넣기
      2. 넣은 리스트의 길이가 M이면 리스트 출력 후 돌아가기
2. 돌아와서 앞에 있는 녀석 제거
3. 다시 넣기

코드

"""n과 m - (1)"""
n, m = list(map(int, input().split()))
graph = []

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