15666 N과M(12) _python

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

15666번: N과 M (12)

 

 

문제 접근

백트래킹

문제를 읽어보면 끝자리를 계속 바꿔나가니 스택으로 접근하기 가장 알맞아보인다.

스택으로 접근하는데 모든경우를 탐색한다는 것은 dfs를 사용하면 쉽게 풀린다.

 

N과M(9)번을 풀어봐서 쉽게 풀렸다.

https://portable-paper.tistory.com/m/45

 

 

 

 

코드

import sys
input = sys.stdin.readline

"""
1. 2번째로 받은 input인 arr 정렬하기
2. dfs사용
3. dfs 사용해서 나온 결과를 저장해뒀다가 다시 set으로 중복 제거.
"""

N, M = map(int,input().split())
arr = list(map(int,input().split()))
arr.sort()
ans = []
save_output = []
visited = [False] * N

def dfs(x):
    if len(ans)==M:
        # save_output.append(" ".join(ans))
        save_output.append(tuple(ans[:]))
        return
    for i in range(x,N):
        ans.append(arr[i])
        dfs(i)
        ans.pop()

dfs(0)

x = sorted(list(set(save_output)))

for i in x:
    print(*i)