2026 华为OD机试真题 新系统 9月20号 【递增差排列】多语言题解

递增差排列(Java/Py/C/C++/Js/Go)题解

华为OD机试真题 新系统 华为OD上机考试真题新系统 9月20号 200分题型

华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录｜机考题库 + 算法考点详解

题目内容

给定两个正整数

n

n

n 和

k

k

k（其中

1

≤

k

≤

n

≤

8

1 \\leq k \\leq n \\leq 8

1≤k≤n≤8），从

[

1

,

n

]

[1, n]

[1,n] 中选取

k

k

k 个元素，排成长度为

k

k

k 的有序数组，按如下条件筛选排列组合后返回：

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

输入描述

两个正整数，分别代表

n

n

n 和

k

k

k。

输出描述

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

样例1

输入

3 3

输出

2 1 3
2 3 1

说明

• $[1,2,3]$
• $[2,1,3]$
• $[2,3,1]$
• 其余排列均不满足条件。

样例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

k=2

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

解题思路

思路：递归回溯

• 本题题目特征以及数据范围1 <= k <= n <=8决定可以使用递归回溯进行解决。利用递归回溯算法从[1,n]枚举选出k个互异整数并满足相邻绝对值差严格递增的合法排列。
• 递归回溯过程中使用vis数组表示数字是否已选择？使用path存储之前已经枚举确定合法序列部分，使用ans保存所有合法序列
• 每一层递归中，将 i 按照1-n顺序尝试放置(可以保证生成序列天然满足升序)，并进行如下判断
  • vis[i] == true： 已被使用，不能选择直接跳过。
  • 检查相邻差绝对值是否满足递增：
    • path.size() <= 1： 直接加入当前数字，更新vis[i] = true, path.push_back(i), 往下递归。
    • path.size() > 1: 需要检查当前数字加入后，后三个数是否满足绝对值之差严格递增。满足情况下 更新vis[i] = true, path.push_back(i), 往下递归。
• 递归结束条件为path.size() == k, 然后进行回溯，搜索不同路径。

C++

#include<bits/stdc++.h>
#include <vector>
using namespace std;

void dfs(int n, int k, vector<bool>& vis, vector<int>& path, vector<vector<int>>& ans) {
int m = path.size();
if (m == k) {
ans.push_back(path);
return;
}
// 从小到大枚举，生成结果天然满足字典序升序规则
for (int i = 1; i <= n; i++) {
// 不能选择重复元素
if (vis[i]) {
continue;
}
// 加入当前少于3个，无需检查
if (m <= 1) {
path.push_back(i);
vis[i] = true;
dfs(n, k, vis, path, ans);
vis[i] = false;
path.pop_back();
// 加入当前数达到3个，检查合规性
} else {
int lastOne = path[m –1];
int lastTwo = path[m – 2];
if (abs(lastTwo – lastOne) < abs(lastOne – i)) {
path.push_back(i);
vis[i] = true;
dfs(n, k, vis, path, ans);
vis[i] = false;
path.pop_back();
}
}
}
}

vector<vector<int>> solve(int n, int k) {
vector<vector<int>> ans;
vector<bool> vis(n + 1, false);
vector<int> path;
dfs(n, k, vis, path, ans);
return ans;
}

int main() {
int n, k;
cin >> n >> k;
vector<vector<int>> ans = solve(n, k);
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans[i].size(); j++) {
if (j > 0) {
cout << " ";
}
cout << ans[i][j];
}
cout << endl;
}
}

JAVA

import java.util.*;

public class Main {

static void dfs(int n, int k, boolean[] vis, List<Integer> path, List<List<Integer>> ans) {
int m = path.size();

if (m == k) {
ans.add(new ArrayList<>(path));
return;
}

// 从小到大枚举，生成结果天然满足字典序升序规则
for (int i = 1; i <= n; i++) {
// 不能选择重复元素
if (vis[i]) {
continue;
}

// 加入当前少于3个，无需检查
if (m <= 1) {
path.add(i);
vis[i] = true;
dfs(n, k, vis, path, ans);
vis[i] = false;
path.remove(path.size() – 1);

// 加入当前数达到3个，检查合规性
} else {
int lastOne = path.get(m – 1);
int lastTwo = path.get(m – 2);

if (Math.abs(lastTwo – lastOne) < Math.abs(lastOne – i)) {
path.add(i);
vis[i] = true;
dfs(n, k, vis, path, ans);
vis[i] = false;
path.remove(path.size() – 1);
}
}
}
}

static List<List<Integer>> solve(int n, int k) {
List<List<Integer>> ans = new ArrayList<>();
boolean[] vis = new boolean[n + 1];
List<Integer> path = new ArrayList<>();

dfs(n, k, vis, path, ans);

return ans;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int k = sc.nextInt();

List<List<Integer>> ans = solve(n, k);

for (List<Integer> row : ans) {
for (int j = 0; j < row.size(); j++) {
if (j > 0) {
System.out.print(" ");
}
System.out.print(row.get(j));
}
System.out.println();
}
}
}

Python

def dfs(n, k, vis, path, ans):
m = len(path)

if m == k:
ans.append(path[:])
return

# 从小到大枚举，生成结果天然满足字典序升序规则
for i in range(1, n + 1):
# 不能选择重复元素
if vis[i]:
continue

# 加入当前少于3个，无需检查
if m <= 1:
path.append(i)
vis[i] = True
dfs(n, k, vis, path, ans)
vis[i] = False
path.pop()

# 加入当前数达到3个，检查合规性
else:
last_one = path[m – 1]
last_two = path[m – 2]

if abs(last_two – last_one) < abs(last_one – i):
path.append(i)
vis[i] = True
dfs(n, k, vis, path, ans)
vis[i] = False
path.pop()

def solve(n, k):
ans = []
vis = [False] * (n + 1)
path = []

dfs(n, k, vis, path, ans)

return ans

n, k = map(int, input().split())

ans = solve(n, k)

for row in ans:
print(" ".join(map(str, row)))

JavaScript

const readline = require("readline");

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

rl.on("line", line => {
const [n, k] = line.trim().split(/\\s+/).map(Number);

function dfs(n, k, vis, path, ans) {
const m = path.length;

if (m === k) {
ans.push([…path]);
return;
}

// 从小到大枚举，生成结果天然满足字典序升序规则
for (let i = 1; i <= n; i++) {
// 不能选择重复元素
if (vis[i]) {
continue;
}

// 加入当前少于3个，无需检查
if (m <= 1) {
path.push(i);
vis[i] = true;
dfs(n, k, vis, path, ans);
vis[i] = false;
path.pop();

// 加入当前数达到3个，检查合规性
} else {
const lastOne = path[m – 1];
const lastTwo = path[m – 2];

if (Math.abs(lastTwo – lastOne) < Math.abs(lastOne – i)) {
path.push(i);
vis[i] = true;
dfs(n, k, vis, path, ans);
vis[i] = false;
path.pop();
}
}
}
}

function solve(n, k) {
const ans = [];
const vis = new Array(n + 1).fill(false);
const path = [];

dfs(n, k, vis, path, ans);

return ans;
}

const ans = solve(n, k);

for (const row of ans) {
console.log(row.join(" "));
}

rl.close();
});

Go

package main

import (
"bufio"
"fmt"
"math"
"os"
)

func dfs(n, k int, vis []bool, path []int, ans *[][]int) {
m := len(path)

if m == k {
temp := make([]int, len(path))
copy(temp, path)
*ans = append(*ans, temp)
return
}

// 从小到大枚举，生成结果天然满足字典序升序规则
for i := 1; i <= n; i++ {
// 不能选择重复元素
if vis[i] {
continue
}

// 加入当前少于3个，无需检查
if m <= 1 {
path = append(path, i)
vis[i] = true
dfs(n, k, vis, path, ans)
vis[i] = false
path = path[:len(path)–1]

// 加入当前数达到3个，检查合规性
} else {
lastOne := path[m–1]
lastTwo := path[m–2]

if math.Abs(float64(lastTwo–lastOne)) < math.Abs(float64(lastOne–i)) {
path = append(path, i)
vis[i] = true
dfs(n, k, vis, path, ans)
vis[i] = false
path = path[:len(path)–1]
}
}
}
}

func solve(n, k int) [][]int {
ans := make([][]int, 0)
vis := make([]bool, n+1)
path := make([]int, 0)

dfs(n, k, vis, path, &ans)

return ans
}

func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()

var n, k int
fmt.Fscan(in, &n, &k)

ans := solve(n, k)

for _, row := range ans {
for j, value := range row {
if j > 0 {
fmt.Fprint(out, " ")
}
fmt.Fprint(out, value)
}
fmt.Fprintln(out)
}
}

C语言

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void dfs(int n, int k, bool vis[], int path[], int m,
int ans[][10], int *ansSize) {
if (m == k) {
for (int i = 0; i < k; i++) {
ans[*ansSize][i] = path[i];
}
(*ansSize)++;
return;
}

// 从小到大枚举，生成结果天然满足字典序升序规则
for (int i = 1; i <= n; i++) {
// 不能选择重复元素
if (vis[i]) {
continue;
}

// 加入当前少于3个，无需检查
if (m <= 1) {
path[m] = i;
vis[i] = true;

dfs(n, k, vis, path, m + 1, ans, ansSize);

vis[i] = false;

// 加入当前数达到3个，检查合规性
} else {
int lastOne = path[m – 1];
int lastTwo = path[m – 2];

if (abs(lastTwo – lastOne) < abs(lastOne – i)) {
path[m] = i;
vis[i] = true;

dfs(n, k, vis, path, m + 1, ans, ansSize);

vis[i] = false;
}
}
}
}

void solve(int n, int k, int ans[][10], int *ansSize) {
bool vis[105] = {false};
int path[10];

dfs(n, k, vis, path, 0, ans, ansSize);
}

int main() {
int n, k;
scanf("%d %d", &n, &k);

int ans[100000][10];
int ansSize = 0;

solve(n, k, ans, &ansSize);

for (int i = 0; i < ansSize; i++) {
for (int j = 0; j < k; j++) {
if (j > 0) {
printf(" ");
}
printf("%d", ans[i][j]);
}
printf("\\n");
}

return 0;
}

​