[백준] 15666번: N과 M (12)

문제

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

풀이

백트래킹을 활용한 풀이
코드 흐름은 주석 참고

import sys

sys.stdin = open('data.txt', 'r')

N, M = map(int, input().split())  # N과 M을 입력 받습니다.
numbers = sorted(list(map(int, input().split())))  # 숫자들을 오름차순으로 정렬하여 리스트로 저장합니다.
result = []  # 조합 결과를 저장할 리스트입니다.


def dfs(start, numbers, N, M):
    if len(result) == M:  # M개의 숫자를 선택한 경우 결과를 출력합니다.
        print(*result)
        return
    pre_number = 0  # 이전에 선택한 숫자를 기록하는 변수입니다.
    for i in range(start, N):
        if pre_number != numbers[i]:  # 중복되는 숫자를 건너뜁니다.
            result.append(numbers[i])  # 숫자를 선택합니다.
            dfs(i, numbers, N, M)  # 재귀적으로 다음 숫자를 선택합니다.
            pre_number = numbers[i]  # 현재 숫자를 이전 숫자로 기록합니다.
            result.pop()  # 결과 리스트에서 선택한 숫자를 제거하여 다른 경우의 수를 탐색합니다.
    return


def solution(N, M, numbers):
    dfs(0, numbers, N, M)  # dfs 함수를 호출하여 조합을 구합니다.
    return


solution(N, M, numbers)  # solution 함수를 호출하여 실행합니다.