题目内容

给定两个正整数 $n$ 和 $k$（其中 $1 \leq k \leq n \leq 8$），从 $[1, n]$ 中选取 $k$ 个元素，排成长度为 $k$ 的有序数组，按如下条件筛选排列组合后返回：

1. 数组中的元素取自整数 $[1, n]$，且互不相同。
2. 对于数组中任意连续三个元素 $a[i], a[i+1], a[i+2]$（即长度至少为 $3$ 时），必须满足：$$\text{abs}(a[i] - a[i+1]) < \text{abs}(a[i+1] - a[i+2])$$
3. 当 $k < 3$ 时，不存在需要检查的连续三个元素，条件 $2$ 视为自动满足。

请按字典序升序返回所有可能的排列。如果不存在，返回空列表。

输入描述

两个正整数，分别代表 $n$ 和 $k$。

输出描述

一个二维数组，包含所有符合条件的排列。

样例1

输入

3,3

输出

[[2,1,3],[2,3,1]]

说明

• $[1,2,3]$：差值为 $|1-2|=1$，$|2-3|=1$，不满足 $1 < 1$（严格递增失败）。
• $[2,1,3]$：差值为 $1, 2$，满足 $1 < 2$ ✅。
• $[2,3,1]$：差值为 $1, 2$，满足 $1 < 2$ ✅。
• 其余排列均不满足条件。

样例2

输入

4,2

输出

[[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]]

说明

因为 $k=2$，序列中只有一对差值，没有后一对进行比较，所以任意两个不同的数字都算满足条件（按字典序输出全部排列）。