[BOJ/PYTHON] 15664. N과 M (10)

백준 문제 링크: https://www.acmicpc.net/problem/15664

문제 요약

N개의 자연수 중에서 M개를 고른 수열

수열은 사전 순으로 증가하는 순서로 출력

고른 수열은 비내림차순이어야 한다.

중복되는 수열을 여러 번 출력하면 안됨

핵심 아이디어

9번 문제에서 비내림차순 조건이 추가되었다. 인덱스를 백트래킹 함수가 인자로 받고, 인덱스 기준부터 for문을 돌리면 된다.

풀이

# silver3-15664. N과 M (10)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nums = list(map(int, input().split()))

nums.sort()
array = []

def back(idx):
    if len(array) == m:
        for i in array:
            print(nums[i], end=' ')
        print()
        return
    last_num = 0
    for i in range(idx, n): 
        if i not in array:
            if nums[i] != last_num:
                array.append(i)
                last_num = nums[i]
                back(i)
                array.pop()

back(0)

실행 시간

메모리 31256KB, 시간 40ms (python3)