15651: N과 M(3)

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

15651번: N과 M (3)

설명

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

핵심 아이디어

• 백트래킹
• 이 문제는 15649와 동일하지만, 중복을 허용하기 때문에, for 문에서 중복을 확인하는 if문이 삭제 되었다.

코드 구현

import sys
input = sys.stdin.readline

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

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