N과M (9)

문제

boj 15655 N과M (9)

풀이

import sys
input = sys.stdin.readline
from itertools import combinations
from itertools import permutations
from itertools import product
from itertools import combinations_with_replacement

n,m = map(int,input().split())
menu = list(map(int,input().split()))
menu.sort()
record = dict()
for i in permutations(menu,m):
  if i not in record:
    record[i] = 1
    print(' '.join(map(str,i)))

재귀

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

arr = list(map(int,input().split()))
# arr.sort()
used = [0] * len(arr)

answer = []

def comb(lst):
    if len(lst) == m:
        answer.append(tuple(lst))
        return


    for i in range(len(arr)):
        if used[i] == 1:
            continue

        used[i] = 1
        comb(lst + [arr[i]])
        used[i] = 0

comb([])
answer = sorted(list(set(answer)))
for tp in answer:
    for i in tp:
        print(i, end=' ')
    print()

주의점

중복을 제거하기위해서 이미 썼던애들을 리스트로 모아두고
새로운거 출력하기전에 그 리스트에 들어있는지 확인하는식으로 돌리면 시간초과 난다.

매번 돌리려면 시간복잡도를 많이 잡아먹으므로 한번에 저장후 set으로 중복제거처리 해주었다.