📌 문제 정보

링크: https://www.acmicpc.net/problem/15657

유형: 백트래킹

난이도: 실버3

스스로 풀었는가? ✅

💻 작성 코드

import sys

N, M = 0, 0
sequence = []
answer = []

def back(cnt, start):
    global N, M, sequence, answer

    if cnt == M:
        print(' '.join(map(str, answer)))
        return
    
    for i in range(start, N):
        answer.append(sequence[i])
        back(cnt + 1, i)
        answer.pop()

readline = sys.stdin.readline
N, M = map(int, readline().split())
sequence = list(map(int, readline().split()))
sequence.sort()

back(0, 0)

🎯 접근 방식

1. 재귀 함수를 통해 길이가 M이 될 때까지 리스트에 값을 하나씩 추가한다.
2. 값을 중복으로 포함할 수 있으므로 값이 현재 순열에 포함되어있는지 확인하지 않는다.
3. 비내림차순으로 정렬되어야 하므로 start를 인자로 넘겨서 해당 값부터 반복문을 돈다.

💡 개선사항

1. print(*answer)으로 쉽게 정답을 출력할 수 있다.

[ktb-algorithm-study] 2주차