[BOJ] 15656. N과 M (7)

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

15656번: N과 M (7)

 

 

1. 해결방법

"""
1. 아이디어
- 입력 리스트를 오름차순으로 리스트에 저장
- 수열의 같은 원소의 중복을 허용하기 때문에 방문기록 x
- 백트래킹 for문 돌면서 해당 원소를 append
- 재귀에서 m개를 선택하면 종료, print

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

3. 자료구조
- 배열 : 입력 int[]
- 백트래킹 : 재귀
"""

 

 

2. 정답코드

 

입력 예제(1)

3 1
4 5 2

출력 예제(1)

2
4
5

 

입력 예제(2)

4 2
9 8 7 1

출력 예제(2)

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

 

입력 예제(3)

3 3
1231 1232 1233

출력 예제(3)

1231 1231 1231
1231 1231 1232
1231 1231 1233
1231 1232 1231
1231 1232 1232
1231 1232 1233
1231 1233 1231
1231 1233 1232
1231 1233 1233
1232 1231 1231
1232 1231 1232
1232 1231 1233
1232 1232 1231
1232 1232 1232
1232 1232 1233
1232 1233 1231
1232 1233 1232
1232 1233 1233
1233 1231 1231
1233 1231 1232
1233 1231 1233
1233 1232 1231
1233 1232 1232
1233 1232 1233
1233 1233 1231
1233 1233 1232
1233 1233 1233

 

 

코드

import sys
input = sys.stdin.readline

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

result = []


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

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


# main
recur(0)