递增差排列
2026 华为OD机试真题9月20日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
题目描述
给定两个正整数 n 和 k（其中 1≤k≤n≤8），从 [1,n] 中选取 k 个元素，排成长度为 k 的有序数组，按如下条件筛选排列组合后返回：
请按字典序升序返回所有可能的排列。如果不存在，返回空列表。
输入描述
两个正整数，分别代表 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，枚举排列并在生成过程中剪枝即可满足要求。
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static List<List<Integer>> solve(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used = new boolean[n + 1];
class Search {
void dfs() {
// 长度达到 k 时，保存当前合法排列
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}
// 按从小到大的顺序选择数字，使结果天然保持字典序
for (int value = 1; value <= n; value++) {
if (used[value]) {
continue;
}
// 新差值必须严格大于前一个差值
if (path.size() >= 2) {
int last = path.size() – 1;
int previousDiff = Math.abs(path.get(last – 1) – path.get(last));
int currentDiff = Math.abs(path.get(last) – value);
if (previousDiff >= currentDiff) {
continue;
}
}
used[value] = true;
path.add(value);
dfs();
path.remove(path.size() – 1);
used[value] = false;
}
}
}
new Search().dfs();
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] parts = scanner.nextLine().trim().split(",");
int n = Integer.parseInt(parts[0].trim());
int k = Integer.parseInt(parts[1].trim());
List<List<Integer>> result = solve(n, k);
StringBuilder output = new StringBuilder("[");
for (int i = 0; i < result.size(); i++) {
if (i > 0) {
output.append(',');
}
output.append('[');
for (int j = 0; j < result.get(i).size(); j++) {
if (j > 0) {
output.append(',');
}
output.append(result.get(i).get(j));
}
output.append(']');
}
output.append(']');
System.out.println(output);
}
}
Python
def solve(n, k):
result = []
path = []
used = [False] * (n + 1)
def dfs():
# 长度达到 k 时，保存当前合法排列
if len(path) == k:
result.append(path.copy())
return
# 按从小到大的顺序选择数字，使结果天然保持字典序
for value in range(1, n + 1):
if used[value]:
continue
# 新差值必须严格大于前一个差值
if len(path) >= 2:
previous_diff = abs(path[–2] – path[–1])
current_diff = abs(path[–1] – value)
if previous_diff >= current_diff:
continue
used[value] = True
path.append(value)
dfs()
path.pop()
used[value] = False
dfs()
return result
n, k = map(int, input().strip().split(","))
answer = solve(n, k)
print("[" + ",".join("[" + ",".join(map(str, row)) + "]" for row in answer) + "]")
JavaScript
const readline = require("readline");
function solve(n, k) {
const result = [];
const path = [];
const used = Array(n + 1).fill(false);
function dfs() {
// 长度达到 k 时，保存当前合法排列
if (path.length === k) {
result.push([…path]);
return;
}
// 按从小到大的顺序选择数字，使结果天然保持字典序
for (let value = 1; value <= n; value++) {
if (used[value]) {
continue;
}
// 新差值必须严格大于前一个差值
if (path.length >= 2) {
const previousDiff = Math.abs(path[path.length – 2] – path[path.length – 1]);
const currentDiff = Math.abs(path[path.length – 1] – value);
if (previousDiff >= currentDiff) {
continue;
}
}
used[value] = true;
path.push(value);
dfs();
path.pop();
used[value] = false;
}
}
dfs();
return result;
}
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
terminal: false
});
rl.on("line", (line) => {
const [n, k] = line.trim().split(",").map(Number);
const answer = solve(n, k);
console.log("[" + answer.map(row => "[" + row.join(",") + "]").join(",") + "]");
rl.close();
});
C++
#include <cstdlib>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> solve(int n, int k) {
vector<vector<int>> result;
vector<int> path;
vector<bool> used(n + 1, false);
function<void()> dfs = [&]() {
// 长度达到 k 时，保存当前合法排列
if (static_cast<int>(path.size()) == k) {
result.push_back(path);
return;
}
// 按从小到大的顺序选择数字，使结果天然保持字典序
for (int value = 1; value <= n; ++value) {
if (used[value]) {
continue;
}
// 新差值必须严格大于前一个差值
if (path.size() >= 2) {
int previousDiff = abs(path[path.size() – 2] – path.back());
int currentDiff = abs(path.back() – value);
if (previousDiff >= currentDiff) {
continue;
}
}
used[value] = true;
path.push_back(value);
dfs();
path.pop_back();
used[value] = false;
}
};
dfs();
return result;
}
int main() {
int n, k;
char comma;
cin >> n >> comma >> k;
vector<vector<int>> answer = solve(n, k);
cout << '[';
for (size_t i = 0; i < answer.size(); ++i) {
if (i > 0) {
cout << ',';
}
cout << '[';
for (size_t j = 0; j < answer[i].size(); ++j) {
if (j > 0) {
cout << ',';
}
cout << answer[i][j];
}
cout << ']';
}
cout << "]\\n";
return 0;
}
Go
package main
import (
"bufio"
"fmt"
"os"
"strings"
)
func solve(n int, k int) [][]int {
result := make([][]int, 0)
path := make([]int, 0, k)
used := make([]bool, n+1)
var dfs func()
dfs = func() {
// 长度达到 k 时，保存当前合法排列
if len(path) == k {
row := append([]int(nil), path…)
result = append(result, row)
return
}
// 按从小到大的顺序选择数字，使结果天然保持字典序
for value := 1; value <= n; value++ {
if used[value] {
continue
}
// 新差值必须严格大于前一个差值
if len(path) >= 2 {
previousDiff := path[len(path)–2] – path[len(path)–1]
if previousDiff < 0 {
previousDiff = –previousDiff
}
currentDiff := path[len(path)–1] – value
if currentDiff < 0 {
currentDiff = –currentDiff
}
if previousDiff >= currentDiff {
continue
}
}
used[value] = true
path = append(path, value)
dfs()
path = path[:len(path)–1]
used[value] = false
}
}
dfs()
return result
}
func main() {
var n, k int
fmt.Scanf("%d,%d", &n, &k)
answer := solve(n, k)
var output strings.Builder
output.WriteByte('[')
for i, row := range answer {
if i > 0 {
output.WriteByte(',')
}
output.WriteByte('[')
for j, value := range row {
if j > 0 {
output.WriteByte(',')
}
fmt.Fprint(&output, value)
}
output.WriteByte(']')
}
output.WriteByte(']')
writer := bufio.NewWriter(os.Stdout)
fmt.Fprintln(writer, output.String())
writer.Flush()
}
C语言
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 8
#define MAX_RESULTS 40320
typedef struct {
int count;
int rows[MAX_RESULTS][MAX_N];
} Result;
typedef struct {
int n;
int k;
int path[MAX_N];
int used[MAX_N + 1];
Result *result;
} SearchContext;
void dfs(SearchContext *context, int depth) {
if (depth == context->k) {
for (int i = 0; i < context->k; ++i) {
context->result->rows[context->result->count][i] = context->path[i];
}
context->result->count++;
return;
}
for (int value = 1; value <= context->n; ++value) {
if (context->used[value]) {
continue;
}
if (depth >= 2) {
int previousDiff = abs(context->path[depth – 2] – context->path[depth – 1]);
int currentDiff = abs(context->path[depth – 1] – value);
if (previousDiff >= currentDiff) {
continue;
}
}
context->used[value] = 1;
context->path[depth] = value;
dfs(context, depth + 1);
context->used[value] = 0;
}
}
Result *solve(int n, int k) {
static Result result;
SearchContext context = {0};
// 初始化搜索状态，并从空排列开始回溯
result.count = 0;
context.n = n;
context.k = k;
context.result = &result;
dfs(&context, 0);
return &result;
}
int main(void) {
int n, k;
scanf("%d,%d", &n, &k);
Result *answer = solve(n, k);
printf("[");
for (int i = 0; i < answer->count; ++i) {
if (i > 0) {
printf(",");
}
printf("[");
for (int j = 0; j < k; ++j) {
if (j > 0) {
printf(",");
}
printf("%d", answer->rows[i][j]);
}
printf("]");
}
printf("]\\n");
return 0;
}
完整用例
用例1
3,3
用例2
4,2
用例3
1,1
用例4
2,2
用例5
5,1
用例6
4,3
用例7
4,4
用例8
5,4
用例9
8,4
用例10
8,8
