[Python] 백준 15663 N과 M (9)

15663번: N과 M (9)

백트래킹 : 중복되는 수열을 제외해야한다. 2 4 4가 있고 길이가 2이면 2 - 4(첫번째 4) 2 - 4(두번째 4)가 중복된다. 주어진 수를 제거하면 안되는게 2 4 4에서 중복되는 4를 제거하면 2 4가 되어 4 - 4 수열을 체크 못한다. 그래서 중복되는 값을 없애야하고 자연스럽게 in을 사용했지만, in은 시간복잡도가  list와 tuple일때 O(N)이지만 set, dict일때 O(1)이다. 그래서 set을 사용했다.

 

전체코드

import sys
import copy

input = sys.stdin.readline


def bt(t, result_each, visited_each):
    if t == 0:
        if tuple(result_each) not in result_total:
            result_total.add(tuple(result_each))
            print(*result_each)
        return
    for i in range(N):
        if i not in visited_each:
            bt(t - 1, result_each + [nums[i]], visited_each + [i])


N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
result_total = set()
bt(M, [], [])