15652: N과 M(4)

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

설명

핵심 아이디어

• 백트래킹
• 현재 dfs의 for문에서 넣은 숫자보다 같거나 커야한다. (비내림차순). 파라미터로 넘겨주어서 체크한다.
• 파라미터로 받은 숫자보다 같거나 커야하기 때문에 start이상 n이하.
• 수를 더해 주고 그 더한 수를 파라미터로 가지고 dfs 호출.
• 원래 상태로 돌리기 위해 pop

코드 구현

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
# 수열을 담는 배열
arr = []

def dfs(start):
	if len(arr) == m:
		print(' '.join(map(str, arr)))
		return
	else:
		# 파라미터로 받은 숫자보다 크거나 같아야한다.
		for i in range(start, n+1):
			# 수를 더해 준다.
			arr.append(i)
			# 더한 수를 파라미터로 다시 dfs
			dfs(i)
			# 원상태로 돌리기 위한 pop
			arr.pop()
dfs(1)