[BOJ] 15649, 15650번 N과 M (1),(2) (Python)

처음에는 순열, 조합을 계산해주는 itertools의 permutations, combinations를 이용했다.

import sys
from itertools import permutations

input = sys.stdin.readline

N,M = map(int,input().split())

nums = [i for i in range(1,N+1)]
for one_tuple in list(permutations(nums,M)):
  print(*one_tuple)

import sys
from itertools import combinations

input = sys.stdin.readline

N,M = map(int,input().split())

nums = [i for i in range(1,N+1)]
for one_tuple in list(combinations(nums,M)):
  print(*one_tuple)

itertools를 이용하지 않고, 순열, 조합을 구현해보려 했는데, 생각보다 쉽게 방법이 떠오르지 않았다.

DFS에서의 풀이를 떠올리며 풀이

import sys
input = sys.stdin.readline

N,M = map(int,input().split())

nums=[]
def dfs(depth):
  if depth == M:
    print(' '.join(nums))
    return

  for i in range(1,N+1):
    if str(i) not in nums: # nums가 visited의 역할도 수행
      nums.append(str(i))
      dfs(depth+1)
      nums.pop()

dfs(0)

import sys
input = sys.stdin.readline

N,M = map(int,input().split())

nums=[]
def dfs(start):
    if len(nums)==M:
        print(' '.join(nums))
        return
    
    for i in range(start,N+1):
        if str(i) not in nums: # nums가 visited의 역할도 수행
            nums.append(str(i))
            dfs(i+1)
            nums.pop()
dfs(1)

아직까지 재귀를 편하게 구현하지 못한다! DFS 관련 문제를 더 풀어보자.