[BOJ] 15654. N과 M (5)

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

15654번: N과 M (5)

 

 

1. 해결방법

"""
1. 아이디어
- 입력을 리스트로 저장
- 백트래킹 재귀함수 안에서, 리스트 안을 for문으로 돌면서 숫자 선택, 방문기록 체크
- 재귀함수에서 M개를 선택할 경우 print

2. 시간복잡도
- N! : 가능

3. 자료구조
- 재귀
- 배열 : 결과 int[]
"""

 

 

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 1
7 8
7 9
8 1
8 7
8 9
9 1
9 7
9 8

 

입력 예제(3)

4 4
1231 1232 1233 1234

출력 예제(3)

1231 1232 1233 1234
1231 1232 1234 1233
1231 1233 1232 1234
1231 1233 1234 1232
1231 1234 1232 1233
1231 1234 1233 1232
1232 1231 1233 1234
1232 1231 1234 1233
1232 1233 1231 1234
1232 1233 1234 1231
1232 1234 1231 1233
1232 1234 1233 1231
1233 1231 1232 1234
1233 1231 1234 1232
1233 1232 1231 1234
1233 1232 1234 1231
1233 1234 1231 1232
1233 1234 1232 1231
1234 1231 1232 1233
1234 1231 1233 1232
1234 1232 1231 1233
1234 1232 1233 1231
1234 1233 1231 1232
1234 1233 1232 1231

 

 

코드

import sys
input = sys.stdin.readline

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

# 방문기록
chk = [False] * (n + 1)
# 결과
result = []


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

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


# main
recur(0)