[BOJ][python] 15666. N과 M (12)

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

15666번: N과 M (12)

---

💡IDEA

백트래킹을 사용하는 문제이다.

백준에 N과 M 문제가 많은데, 12번 쯤 되면 순열을 조건별로 구할 수 있는 달인이 되었을 것이다.

15657. N과 M (8) 과 15663. N과 M (9) 두 문제를 적절하게 섞어서 풀 수 있는 문제다.

같은 수를 여러 번 골라도 되고, 비내림차순인 수열을 구한다.

같은 수 중복 허용이므로 반복문의 시작점은 idx 부터이고, tmp를 통해 중복되는 수열은 없도록 한다. 

📌CODE

import sys
input = sys.stdin.readline

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

def permutation(idx, perm):
    if len(perm) == M:
        print(*perm)
        return
    tmp = 0
    for i in range(idx, N):
        if tmp != numbers[i]:
            perm.append(numbers[i])
            tmp = numbers[i]
            permutation(i, perm)
            perm.pop()

permutation(0, [])