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

1. 문제

15663번: N과 M (9)

2. 개요

백트래킹문제.

조건은 중복원소X, 중복수열X, 비내림차순 출력이다.

3. 코드 및 추가 설명

import sys

N, M = map(int, sys.stdin.readline().split())

nums = sorted(list(map(int, sys.stdin.readline().split())))
ans = []

def bt(idx = 0, l = [], k = []):
    global ans
    if idx == M and l not in ans:
        ans.append(l)
        print(*l)

    for i in range(N):
        if i not in k:
            bt(idx + 1, l + [nums[i]], k + [i])

bt()

원래는 미리 정렬을 하고 걸러가면서 답을 추가하는 식으로 짜봤었는데 시간초과가 떴다.

import sys

N, M = map(int, sys.stdin.readline().split())

nums = list(map(int, sys.stdin.readline().split()))
ans = []

def bt(idx = 0, l = [], k = []):
    global ans
    if idx == M:
        ans.append(l)

    for i in range(N):
        if i not in k:
            bt(idx + 1, l + [nums[i]], k + [i])

bt()

ans = list(map(tuple, ans))
ans = sorted(list(set(ans)))

for a in ans:
    print(*a)

그래서 일단 중복원소만 거른 채 다 구해보고 중복수열을 빼고 정렬해서 출력했더니 성공했다.