[BOJ/PYTHON] 15657. N과 M (8)

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

문제 요약

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

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

같은 수를 여러 번 골라도 된다.

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

핵심 아이디어

인덱스 백트래킹을 해준다. 백트래킹하는 수를 담은 배열에는 실제 값을 넣어주고, 인덱스 기준으로 백트래킹하면 된다.

풀이

# silver3-15657. N과 M (8)

import sys
input = sys.stdin.readline

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

nums.sort()
array = []

def back(i):
    if len(array) == m:
        print(*array)
        return
    for idx in range(i, n):
        array.append(nums[idx])
        back(idx)
        array.pop()

back(0)

실행 시간

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