[백준 15655번] 파이썬 - N과 M(6)

백준 15655 - N과 M(6)

시간 제한 1초, 메모리 제한 512MB

# 조건

• N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
  • N개의 자연수 중에서 M개를 고른 수열
  • 고른 수열은 오름차순이어야 한다.

입력

• 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
• 둘째 줄에 N개의 수가 주어진다.
  • 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

• 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.
• 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
• 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

# 접근 방법

• 전형적인 백트래킹 문제이다.
• 조합을 사용하여 바로 combination 함수를 가져다 사용해도 되지만 직접 backtracking을 구현해주었다.
• 순열과 다른 점은 순서가 상관없기 때문에 함수의 인자로 i+1을 넣어주어 더 작은 수가 들어오지 못하게 해주었다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

def backtracking(idx, cnt):
    if cnt == M:
        print(*temp)
        return

    for i in range(idx, N):
        if not visited[i]:
            temp.append(nums[i])
            visited[i] = True
            backtracking(i+1, cnt+1)
            temp.pop()
            visited[i] = False

if __name__ == '__main__':
    N, M = map(int, input().split())
    nums = list(map(int, input().split()))
    nums.sort()
    temp = []

    visited = [False] * N
    backtracking(0, 0)