[BOJ] 15655. N과 M (6)

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

15655번: N과 M (6)

 

 

1. 해결방법

"""
1. 아이디어
- 입력을 리스트로 받고 오름차순으로 정렬
- 백트래킹으로 for문을 돌면서 stack없는 문자를 append, 방문기록 체크
- 수열이 중복되지 않도록 하고, 직전 문자보다 크게 사전 순으로 증가
- 재귀에서 m개를 선택 시 종료, print

2. 시간복잡도
- N! (N <= 7): 가능

3. 자료구조
- 배열 : 입력 int[], 방문기록 bool[][]
- 백트래킹 재귀

"""

 

 

2. 정답코드

 

입력 예제(1)

3 1
4 5 2

출력 예제(1)

2
4
5

 

입력 예제(2)

4 2
9 8 7 1

출력 예제(2)

1 7
1 8
1 9
7 8
7 9
8 9

 

입력 예제(3)

4 4
1231 1232 1233 1234

출력 예제(3)

1231 1232 1233 1234

 

 

코드

import sys
input = sys.stdin.readline

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

result = []
chk = [False] * (n + 1)


# recur
def recur(num):
    # 재귀 종료 지점
    if len(result) == m:
        print(' '.join(map(str, result)))
        return

    # 재귀
    for i in range(num, n + 1):
        if chk[i] == False:
            chk[i] = True
            result.append(number[i-1])
            recur(i + 1)
            result.pop()
            chk[i] = False



# main
recur(1)