LeetCode 1718中等回溯 · 枚举
构建字典序最大的可行序列 图解题解
这道题到底在问什么
把要求钉成三条。第一,数字 1 在整串里只出现一次。第二,2 到 n 之间的每个数都恰好出现两次。第三,对每个 2 到 n 的数 v,它两次出现的下标要相差正好 v,也就是两个 v 的距离等于 v 本身。满足这些的序列长度固定是 2 乘 n 再减 1。这样的序列往往不止一种,我们要挑字典序最大的那一个,也就是越靠前的位置数字越大越好。题目保证在给定 n 下一定有解。下面用 n 等于 4 演示,序列长 7,下标从 0 到 6。
- 输入
- n = 3
- 输出
- [3, 1, 2, 3, 2] (两个 3 相距 3, 两个 2 相距 2)
- 输入
- n = 4
- 输出
- [4, 2, 3, 2, 4, 3, 1] (本节演示)
- 输入
- n = 5
- 输出
- [5, 3, 1, 4, 3, 5, 2, 4, 2]
先想最直接的笨办法
到下标 2。先看最大的 4,已经放满,跳过;再看 3,3 还没放过,试试它。（动画第 12 步）
最优解：一步一步想明白
- 3记牢这套:逐位从左往右填,每个空位先试最大的数,把 v 放在 p 就要求伙伴位 p+v 在界内且空着;放下去递归,走死就撤回换小一号。数字 1 只放一个。
- 4先看画面怎么摆。上面这一排 7 个格子就是要填的序列,下标 0 到 6,现在全是空的,用点号占位。右边「数字放置进度」列着 4、3、2、1,现在都还没放。我们从下标 0 开始,一格一格往右填,每个空位都先抢着放最大的数,好让整串字典序尽量大。
- 5先把最关键的距离约束讲透。对数字 v,它的两次出现下标要正好相差 v。比如待会儿把 4 放在下标 0,那它的另一处就被死死钉在下标 0 加 4 也就是 4 的位置;把 2 放在下标 1,另一处就钉在 1 加 2 等于 3。所以每放一个数,其实是一次定下两格。因为要字典序最大,靠前的位置数字越大越好,我们就让每个空位都先试最大的。
- 6从下标 0 起手,试还没放过的最大的数 4。把 4 放这里,它的伙伴位就是 0 加 4 等于 4。下标 4 落在序列长度 7 以内,不越界;而且现在是空的。两条都满足,4 可以放。
- 7把 4 的两处都放下,下标 0 和下标 4 都填 4,这两格标绿。你看它俩的距离,4 减 0 正好是 4,符合约束。字典序最大的诀窍就在这:先把能放的最大数顶到最前面。接着去填下标 1。
- 8来到下标 1,还是先想最大的。4 已经两处都放完了,进度面板里 4 是「已放」,跳过它,退一档去试第二大的 3。
- 9试着把 3 放在下标 1,那它的伙伴位是 1 加 3 等于 4。可是下标 4 已经被前面的 4 占住了,这一格标红提醒。3 的第二处没地方落,放不进去,只能再退一档,去试更小的 2。这一步的退档,正是回溯里「此路不通就换一个」的味道。
- 10改试 2。把 2 放在下标 1,伙伴位是 1 加 2 等于 3。下标 3 在界内,而且现在空着,两条都过关,2 可以放。
- 11把 2 的两处放下,下标 1 和下标 3 都填 2,标绿。距离一验,3 减 1 等于 2,正好等于 2 本身,合法。现在序列长成 4、2、空、2、4、空、空。指针继续右移到下标 2。
- 12到下标 2。先看最大的 4,已经放满,跳过;再看 3,3 还没放过,试试它。
- 13把 3 放在下标 2,伙伴位是 2 加 3 等于 5。下标 5 在界内,而且现在空着,两条都满足,3 可以放。
- 14把 3 的两处放下,下标 2 和下标 5 都填 3,标绿。距离验一下,5 减 2 等于 3,正好符合。现在序列是 4、2、3、2、4、3、空,只剩最后一格下标 6 空着了。
- 15指针走到下标 3,发现这里早就是 2 了。它是刚才放 2 时定下的第二处,不用再管,指针直接右移。
- 16下标 4 也已经是 4,那是最开始放 4 时钉下的第二处,同样跳过,继续右移。
- 17下标 5 已经是 3,是刚放 3 时定下的第二处,跳过。指针走到最后一格下标 6。
- 18到最后一格下标 6。看进度面板,4、3、2 都已经两处放满了。只剩数字 1 还没登场,而 1 全场只放一个,正好安排在这最后的空位。
- 19把 1 放在下标 6。1 只出现一次,没有伙伴位要照顾,直接落下,标绿。所有 7 个格子都填满了,一条完整合法的序列成型:4、2、3、2、4、3、1。
- 20成型了,回头逐个数验一遍距离。先看 4,它落在下标 0 和下标 4,两处相距 4 减 0 等于 4,正好等于 4 本身,合法。
- 21再看 2,它落在下标 1 和下标 3,相距 3 减 1 等于 2,等于 2 本身,合法。
- 22接着看 3,它落在下标 2 和下标 5,相距 5 减 2 等于 3,等于 3 本身,合法。
- 23最后看 1,它只在下标 6 出现这一次,题目就要求 1 只放一个,符合。四个数字全部验过,这确实是一条合法序列。
- 24收个尾。它之所以是字典序最大,是因为每个空位都从大到小试,只有后续能把整串填满,这个数才保留下来;本例从头到尾一路成功,所以排出 [4, 2, 3, 2, 4, 3, 1],跟开头说的对上了。正因为是从大到小搜索,第一条凑齐的完整合法序列就是字典序最大解。多说一句:n 等于 4 这一趟从大到小恰好一路顺,没真正撤销过整段;但换成 n 等于 5,中途就会走死一次,得把放下的数撤回来退一档,那时回溯的「退」才真正派上用场。
⚠️ 容易写错的地方
✗ 错：把伙伴位算错或漏了越界判断
✓ 对：数 v 放在下标 p 时,伙伴位是 p 加 v,它必须在界内且那格为空才合法
距离约束是这题的命脉,伙伴位既要不越出序列长度,也不能落在已被占的格子上;两个条件漏了任何一个,都会排出一条违反距离要求的非法序列
✗ 错：以为纯贪心从大到小放就行,不写撤销
✓ 对：放下去要递归,一旦后面填不下去,必须把这次放的数撤回来退一档
n 等于 4 恰好一路顺让人误以为不用回溯,但换成 n 等于 5 就会走进死路,少了撤销这一步对这些 n 直接得不到解。撤销是回溯的骨架,不能省
✗ 错：把数字 1 也当成放两次
✓ 对：1 只放一个,cnt[1] 初始化成 1,其余数字才是 2
题目里 1 是特例只出现一次,如果 cnt[1] 也设成 2,程序会试图放两个 1、还去给它找伙伴位,整串长度和内容全乱套
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def constructDistancedSequence(self, n: int) -> List[int]:
def dfs(u):
if u == n * 2:
return True
if path[u]:
return dfs(u + 1)
for i in range(n, 1, -1):
if cnt[i] and u + i < n * 2 and path[u + i] == 0:
cnt[i] = 0
path[u] = path[u + i] = i
if dfs(u + 1):
return True
path[u] = path[u + i] = 0
cnt[i] = 2
if cnt[1]:
cnt[1], path[u] = 0, 1
if dfs(u + 1):
return True
path[u], cnt[1] = 0, 1
return False
path = [0] * (n * 2)
cnt = [2] * (n * 2)
cnt[1] = 1
dfs(1)
return path[1:]C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
int n;
vector<int> cnt, path;
vector<int> constructDistancedSequence(int _n) {
n = _n;
cnt.resize(n * 2, 2);
path.resize(n * 2);
cnt[1] = 1;
dfs(1);
vector<int> ans;
for (int i = 1; i < n * 2; ++i) ans.push_back(path[i]);
return ans;
}
bool dfs(int u) {
if (u == n * 2) return 1;
if (path[u]) return dfs(u + 1);
for (int i = n; i > 1; --i) {
if (cnt[i] && u + i < n * 2 && !path[u + i]) {
path[u] = path[u + i] = i;
cnt[i] = 0;
if (dfs(u + 1)) return 1;
cnt[i] = 2;
path[u] = path[u + i] = 0;
}
}
if (cnt[1]) {
path[u] = 1;
cnt[1] = 0;
if (dfs(u + 1)) return 1;
cnt[1] = 1;
path[u] = 0;
}
return 0;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
private int[] path;
private int[] cnt;
private int n;
public int[] constructDistancedSequence(int n) {
this.n = n;
path = new int[n * 2];
cnt = new int[n * 2];
Arrays.fill(cnt, 2);
cnt[1] = 1;
dfs(1);
int[] ans = new int[n * 2 - 1];
for (int i = 0; i < ans.length; ++i) {
ans[i] = path[i + 1];
}
return ans;
}
private boolean dfs(int u) {
if (u == n * 2) {
return true;
}
if (path[u] > 0) {
return dfs(u + 1);
}
for (int i = n; i > 1; --i) {
if (cnt[i] > 0 && u + i < n * 2 && path[u + i] == 0) {
cnt[i] = 0;
path[u] = i;
path[u + i] = i;
if (dfs(u + 1)) {
return true;
}
cnt[i] = 2;
path[u] = 0;
path[u + i] = 0;
}
}
if (cnt[1] > 0) {
path[u] = 1;
cnt[1] = 0;
if (dfs(u + 1)) {
return true;
}
cnt[1] = 1;
path[u] = 0;
}
return false;
}
}复杂度
时间
最坏指数级
这是一棵回溯搜索树:每个空位都可能从大到小试多个数、每个数放下去又往深里递归,最坏情况下要探很多条分支,难以给出漂亮的多项式上界,通常按指数级看待。好在两条约束砍掉大量分支:一是每个数的伙伴位被距离死死钉住,能放的位置很少;二是从大到小试、第一个能成的就锁定。所以 n 不超过 20 时,实际探到的分支很少,很快出解
空间
O(n)
按峰值算。path 数组和 cnt 数组都是 2n 长度,是 O(n);递归最深也就填到序列末尾,深度不超过 2n 层,递归栈也是 O(n)。两者都是 O(n),合起来 O(n),和序列长度同量级
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 构建字典序最大的可行序列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题能不能不用回溯,直接套个构造公式排出来?+
有些 n 确实存在规律构造,但公式并不通用,也不好保证一定给出字典序最大的那一串。回溯从大到小试、配上距离约束自动剪枝,既能保证字典序最大,又因为题目保证有解而一定能填满,是最稳妥的通用解法,所以业界默认用它。
演示里 n 等于 4 从头到尾没真正撤销过,那撤销这步还必须写吗?+
必须写。n 等于 4 只是恰好从大到小一路都放得下,运气好而已。换成 n 等于 5,填到中途就会走进死路,得把先放的数撤回来退一档换小的,这时才填得出解。撤销是回溯的骨架,漏了它对这些 n 直接无解,不能因为小例子没触发就省掉。
复杂度到底怎么估,面试要报个数吗?+
照实说这题复杂度不好精确刻画,是一棵回溯搜索树,最坏按指数级看待。但两条硬约束帮了大忙:每个数的伙伴位被距离钉死、可放位置很少,再加上从大到小试、候选只有能递归填完整串时才锁定(当前可放但后续失败的会被撤销),实际探到的分支远比理论上界少。所以 n 不超过 20 时秒级出解,报一个「最坏指数、剪枝后很快」即可。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 构建字典序最大的可行序列 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。