[실버 2] 백준 15666 - N과 M (12) (파이썬)

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

풀이

• 자연수 N개 중에서 M개를 중복 선택 가능하게 고르되,
• 고른 수열은 비내림차순이어야 하고,
• 중복되는 수열은 한 번만 출력해야 합니다.

N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums = sorted(list(set(nums)))

nums에서 중복 제거 후 정렬한다. 왜냐하면 중복 수열 출력을 방지하기 위해서이다.

def back(start, depth):
    if depth == M:
        print(' '.join(map(str, result)))
        return
    for i in range(start, len(nums)):
        result.append(nums[i])
        back(i, depth + 1)
        result.pop()

백트래킹 함수는 depth가 M이 되면 수열을 완성하고, start부터 시작하는 이유는 비내림차순 조건 때문이다.

코드

# 백준 15666 - N과 M (12)
# 분류 : 백트래킹

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

nums = list(map(int, input().split()))
nums = sorted(list(set(nums)))

result = []

def back(start, depth) :
    if depth == M :
        print(' '.join(map(str, result)))
        return
    for i in range(start, len(nums)) :
        result.append(nums[i])
        back(i, depth + 1)
        result.pop()

back(0, 0)