[Backtracking] 15666 N과 M(12)

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

15666번: N과 M (12)

 

import sys
input = sys.stdin.readline

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

answer = []
def backtracking(start):
    if len(answer) == m:
        print(' '.join(map(str, answer)))
        return 

    tmp = 0
    for i in range(start, n):
        if tmp !=number[i]:
            tmp = number[i]
            answer.append(number[i])
            backtracking(i)
            answer.pop()


backtracking(0)

key point!

1. 고른 수열은 비내림차순이어야 한다.

길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

-> backtracking함수의 매개변수를 통해 비내림차순으로 탐색

 

2. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

-> tmp라는 임시 변수를 통해 중복되는 수열을 제거