백준 15666 N과 M (12)

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

 

 이 문제는 N개의 자연수 중 M개를 중복하여 고른 내림차순 수열을 중복없이 사전순으로 출력하는 문제이다. 이 문제도 DFS를 응용하여 풀면 쉽게 풀 수 있는 문제이다.

def chosing(seq):
    if len(seq) == M+1:
        ans_set.add(tuple(seq[1:]))
        return
    
    for i in Ns:
        if i >= seq[-1]:
            chosing(seq+[i])
    

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

ans_set = set()

chosing([-1])
ans_list = sorted(list(ans_set))

for ans in ans_list:
    print(' '.join(str(a) for a in ans))