BOJ 백준 15663: N과 M (9)

Table of contents

들어가며

BOJ 백준 15664: N과 M (10)풀이와 상당히 비슷합니다.
이번 문제는 수열의 제한 조건에 단조 증가 수열이 아니라서, 일종의 permutation들을 구하는 것이라고 볼 수 있습니다.

AC 받은 Python 코드

import sys

input = sys.stdin.readline


def permutation(cur_len):
    # base condition 1
    if cur_len == M:
        ansSet.add(tuple(seq))
        return

    for i in range(lenNums):
        if isUsed[i]:
            continue
        isUsed[i] = True
        seq.append(nums[i])
        permutation(cur_len + 1)
        isUsed[i] = False
        seq.pop()


if __name__ == "__main__":
    N, M = map(int, input().rstrip().split())
    nums = [*sorted(map(int, input().rstrip().split()))]
    lenNums = len(nums)
    isUsed = [False for _ in range(lenNums)]
    seq = []
    ansSet = set()
    for i in range(lenNums):
        isUsed[i] = True
        seq.append(nums[i])
        permutation(1)
        isUsed[i] = False
        seq.pop()
    for ans in sorted(ansSet):
        print(" ".join(map(str, ans)))