15654 N과M(5) _python

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

15654번: N과 M (5)

 

12개의 비슷한 문제가 있는 문제 (1)~(12)

 

 

문제 접근

백트래킹

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

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

arr을 미리 입력받고 sort해준다.

그리고 N과M(1)과 같은 방식으로 dfs를 해주면 풀릴 것이다.

 

 

 

코드

import sys
input = sys.stdin.readline

"""
1. 2번째로 받은 input인 arr 정렬하기
2. dfs사용
"""

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

def dfs():
    if len(ans)==M:
        print(*ans)
        return
    for i in arr:
        if i not in ans:
            ans.append(i)
            dfs()
            ans.pop()

dfs()