[백준/Python]15655: N과 M (6)

문제

https://www.acmicpc.net/problem/15655
백준 문제집 - 0x0C강 - 백트래킹

 

알고리즘: 백트래킹

---

풀이

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

 

바로 직전의 문제 15645: N과 M (5)과 비슷한 문제다.

하지만 이번엔 만들어진 수열 자체가 오름차순이어야 하므로, 현재 숫자보다 작은 숫자들은 수열에 추가될 수 없다.
따라서 현재 숫자의 인덱스를 나타낼 변수 start를 함수에 같이 넘겨준다.

 

for문으로 start부터 N까지 순회를 진행하는데,
현재 숫자의 다로 다음 인덱스부터 수열에 추가될 수 있으므로 backtrack(현재 숫자의 인덱스+1, 수열)의 형태로 호출한다.

 

전체 코드

# 메모리: 31120KB / 시간: 32ms
from sys import stdin


input = stdin.readline

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))

def backtrack(start, ret):
    if len(ret) == M:
        print(" ".join(map(str, ret)))
        return

    for i in range(start, N):
        ret.append(nums[i])
        backtrack(i+1, ret)
        ret.pop()

backtrack(0, [])