급격한 내림이 없는 배열

면접 대비

시간 제한1초메모리 제한1024 MB

요약

1부터 n까지의 수 중 k개를 서로 다르게 골라 만든 배열 가운데, 인접한 두 수가 1을 넘게 줄어드는 경우가 없는 배열을 사전순으로 모두 출력합니다.

문제

$n$ 에서 $k$ 개를 뽑아 만든 배열은 $1$ 부터 $n$ 까지의 자연수 중 서로 다른 $k$ 개의 수로 이루어진 배열 $a[1..k]$ 이다.

인접한 두 원소 $a[i], a[i+1]$ 에서 $a[i] > a[i+1]$ 이면 이를 내림이라 한다. 내림 중에서 $a[i] > a[i+1] + 1$ 을 만족하는 것을 급격한 내림이라 한다.

$n$ 과 $k$ 가 주어졌을 때, 급격한 내림이 없는 배열을 모두 출력하라. 배열은 첫 번째 수로 정렬하고, 첫 번째 수가 같으면 두 번째 수로, 이후에도 같은 방식으로 정렬한다.

첫 줄에 자연수 $n$ 이, 둘째 줄에 자연수 $k$ 가 주어진다 ( $1 \le k \le n \le 13$ ).

급격한 내림이 없는 $n$ 에서 $k$ 개를 뽑은 배열을 모두 한 줄에 하나씩 출력한다. 배열 안의 수는 공백으로 구분한다.