[Brute Force] Boj15663: N과 M(9)

[Brute Force] Boj15663: N과 M(9)

Link: https://www.acmicpc.net/problem/15663

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

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

입력

• 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
• 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

• 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
• 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

입출력 예제

Code | Python

import sys
si = sys.stdin.readline
n,m = list(map(int,si().split()))
numbers = sorted(list(map(int,si().split())))
selected = [[] for _ in range(m)]
used = [False for _ in range(len(numbers))]

def rec(k):
    if k == m:
        temp = ''
        for x in selected:
            temp += str(x) + " "
        print(temp)
    else:
        lastCand = 0
        for i in range(n):
            if used[i] == False and numbers[i]!=lastCand:
                selected[k] = numbers[i]
                lastCand = numbers[i]
                used[i] = True
                rec(k+1)
                used[i] = False
                selected[k] = 0
rec(0)

Screenshot & Output