2026 华为OD机试真题9月20日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

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

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

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

2026 华为OD机试真题9月20日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

输入描述

两个正整数，分别代表 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，序列中只有一对差值，没有后一对进行比较，所以任意两个不同的数字都算满足条件（按字典序输出全部排列）。

解题思路

本题采用【回溯搜索 + 剪枝】算法：使用 path 记录当前排列，使用 used 标记已经选择的数字，避免同一个数字重复出现。每一层都按 1 到 n 的顺序枚举候选值，因此最终收集到的排列天然满足字典序升序，无需额外排序。

当 path 中已经至少有两个元素时，加入新元素会产生一个新的相邻差值。只有当前差值严格大于前一个差值时才继续递归，否则立即剪枝。k<3 时不会触发该检查，所有互不相同的长度为 k 的排列都会被保留。

搜索到长度 k 后复制当前排列加入答案，再撤销本层选择继续尝试其他数字。由于 n 最大只有 8，枚举排列并在生成过程中剪枝即可满