15655 N과M(6) _python

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

15655번: N과 M (6)

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

 

 

문제 접근

백트래킹

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

스택으로 접근하는데 모든경우를 탐색한다는 것은 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(x):
    if len(ans)==M:
        print(*ans)
        return
    for i in range(x,N):
        if arr[i] not in ans:
            ans.append(arr[i])
            dfs(i)
            ans.pop()

dfs(0)