백준 알고리즘 15663번 N과 M (9)(python)

기본적인 백트래킹 문제이다. 그냥 리스트를 사용해서 중복인지 아닌지 확인하면 무조건 시간초과가 나와서,

딕셔너리(해시)를 사용해서 풀었다. 해시는 진짜 진짜 진짜 엄청 빠르다!!

def dfs(depth):
    if depth == M:
        s = ' '.join(map(str, li))
        if s not in d:
            d[s] = 1
            print(s)
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        check[i] = 0

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
d = {}; li = []
check = [0]*N
dfs(0)