[Backtracking] 15663 N과 M(9)

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

15663번: N과 M (9)

 

# 2022.12.30
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
number = sorted(list(map(int, input().split())))

answer = []
visited = [0]*(n)
def backtracking():
    if len(answer)==m:
        print(' '.join(map(str, answer)))
        return

    tmp=0
    for i in range(0, n):
        if visited[i]==0 and tmp !=number[i]:
            answer.append(number[i])
            visited[i]=1
            tmp=number[i]
            backtracking()
            answer.pop()
            visited[i]=0

backtracking()

key point!

중복되는 수열을 여러 번 출력하면 안된다?

-> visited 리스트를 활용하여 방문 여부를 저장한다

-> tmp라는 임시 변수를 활용하여 중복되는 수열을 탐색하지 않도록 한다

 

수열은 사전 순으로 증가하는 순서로 출력해야 한다?

-> 입력을 받을 때 sort함수를 통해 숫자들을 미리 정렬시켜준다