【算法精讲】回溯+贪心实战：从“小于n的最大数”看字节面试高频考点

1. 从一道面试题看算法组合的威力

第一次看到"小于n的最大数"这道题时，我下意识觉得这不就是个简单的数字组合问题吗？但真正动手实现时才发现，单纯的暴力枚举根本行不通。比如给定n=23121，数字集合A={2,4,9}，要找到小于23121的最大组合数，最直观的想法可能是生成所有可能的组合然后比较，但这样效率太低了。

这道题的精妙之处在于它完美结合了两种经典算法思想：回溯法和贪心算法。回溯法负责系统地探索所有可能的解空间，而贪心算法则在每一步做出局部最优选择，两者结合能大幅提升解题效率。在实际面试中，字节跳动的面试官特别喜欢考察这类算法组合题，因为它能同时检验候选人的基础算法功底和实际问题解决能力。

我曾在面试中遇到过类似的变种题，当时要求找出小于n的最小素数组合。现在回想起来，如果当时掌握了这种算法组合的思路，解题过程会顺利很多。这也是为什么我觉得有必要深入剖析这道题，它不仅是一道面试题，更是一个展示算法思维的好案例。

2. 问题拆解与算法选择

2.1 问题本质分析

让我们先明确问题的具体要求：给定一个数字n和一个数字集合A，要求用A中的数字组合出小于n的最大数字。这里有几个关键点需要注意：

1. 组合数字必须完全来自集合A
2. 结果必须严格小于n
3. 在所有满足条件的数字中取最大值

举个例子，当n=23121，A={2,4,9}时：

• 22999是有效解
• 23121不是解（等于n）
• 24121不是解（大于n且使用了不在A中的数字1）
• 9999不是解（虽然由A中的数字组成，但小于22999）

2.2 为什么选择回溯+贪心？

回溯法特别适合解决这类组合问题，因为它能系统地探索所有可能的解空间。但纯回溯有个明显缺点：当数字位数较多时，组合数量会爆炸式增长，导致效率低下。

这时候贪心算法就能派上用场了。我们可以利用贪心思想进行剪枝：

1. 从最高位开始，尽可能选择大的数字
2. 一旦确定某位比n的对应位小，后面所有位都可以直接填充最大数字
3. 如果某位等于n的对应位，则需要继续谨慎处理下一位

这种组合策略能将时间复杂度从O(|A|^L)降到O(|A|×L)，其中|A|是数字集合大小，L是数字位数。在实际编码面试中，能够识别并实现这种优化往往就是能否通过的关键。

3. 算法实现详解

3.1 预处理阶段

在开始递归之前，我们需要做一些准备工作：

vector<int> sorted_A = A; sort(sorted_A.begin(), sorted_A.end(), greater<int>()); int max_digit = sorted_A[0]; string n_str = to_string(n); int n_len = n_str.length();

这里做了三件事：

1. 将数字集合A降序排序，方便后续从大到小尝试
2. 找出集合中的最大数字，用于后续贪心填充
3. 将n转为字符串，便于逐位比较

降序排序是个小技巧但很实用。在面试中，这样的小优化能展示你对细节的关注。我记得有一次面试，候选人就因为忽略了排序这步，导致算法效率降低，最后与offer失之交臂。

3.2 核心递归逻辑

递归函数是算法的核心，它需要处理以下几种情况：

bool dfsHelper(const string& n_str, int n_len, const vector<int>& sorted_A, int max_digit, vector<int>& path, bool preIsEqual, string& result) { if (!result.empty()) return true; if (path.size() == n_len) { string path_str = ""; for (int digit : path) path_str += to_string(digit); if (path_str < n_str) { result = path_str; return true; } return false; } int pos = path.size(); int n_digit = n_str[pos] - '0'; // 贪心优化1：前面位已小于n，后续填最大数字 if (!preIsEqual) { string path_str = ""; for (int digit : path) path_str += to_string(digit); path_str += string(n_len - path.size(), '0' + max_digit); result = path_str; return true; } // 贪心优化2：从大到小尝试数字 for (int digit : sorted_A) { if (preIsEqual && digit > n_digit) continue; path.push_back(digit); if (preIsEqual && digit < n_digit) { string path_str = ""; for (int d : path) path_str += to_string(d); path_str += string(n_len - path.size(), '0' + max_digit); result = path_str; path.pop_back(); return true; } bool found = dfsHelper(n_str, n_len, sorted_A, max_digit, path, preIsEqual && digit == n_digit, result); if (found) return true; path.pop_back(); } return false; }

这个递归函数有几个关键点：

1. preIsEqual参数记录之前位是否都等于n的对应位
2. 一旦发现preIsEqual为false，立即用最大数字填充剩余位
3. 当前位小于n对应位时，也触发贪心填充
4. 只有当前位等于n对应位时才需要继续递归

3.3 边界情况处理

算法还需要处理一些特殊情况：

1. 当n是单位数时，直接找集合中小于n的最大数
2. 当找不到合适解时，返回位数减一的全最大数字组合

// 处理单位数情况 if (n_len == 1) { int result = -1; for (int digit : sorted_A) { if (digit < n && digit > result) { result = digit; } } return (result == -1) ? "" : to_string(result); } // 处理无解情况 if (!isFound || result.empty()) { return string(n_len - 1, '0' + max_digit); }

这些边界情况在面试中很容易被忽略，但往往就是面试官考察的重点。我有次作为面试官时，特意设置了一个n=1000，A={9}的测试用例，结果很多候选人都没考虑到这种情况。

4. 算法优化与复杂度分析

4.1 贪心剪枝的效果

让我们通过具体例子看看贪心优化的威力。对于n=23121，A={2,4,9}：

1. 第一位尝试9：9>2，跳过
2. 第一位尝试4：4>2，跳过
3. 第一位尝试2：2==2，继续
4. 第二位尝试9：9>3，跳过
5. 第二位尝试4：4>3，跳过
6. 第二位尝试2：2<3，触发贪心填充

此时直接得到结果22999，而不需要继续处理后面三位。如果没有贪心优化，算法会继续递归处理所有位，效率明显降低。

4.2 时间复杂度对比

• 纯回溯：O(|A|^L)，需要探索所有可能的组合
• 回溯+贪心：
  • 最坏情况：O(|A|×L)，当数字与n相同时发生
  • 最好情况：O(L)，当第一位就小于n时发生

在实际应用中，这种优化能带来数量级的性能提升。特别是在处理大数字时，比如L=10，|A|=5的情况下，纯回溯需要处理5^10≈9百万种可能，而优化后最多只需要处理5×10=50种情况。

4.3 空间复杂度分析

空间复杂度主要是递归栈的开销：

• 最坏情况下递归深度为L，所以空间复杂度是O(L)
• 存储结果和中间路径也需要O(L)空间

因此总体空间复杂度是O(L)，这在大多数情况下都是可以接受的。

5. 测试用例设计与验证

5.1 测试用例的重要性

在面试中，写完代码后往往需要自己设计测试用例验证。好的测试用例应该覆盖：

1. 正常情况
2. 边界情况
3. 特殊输入
4. 性能临界点

以下是我总结的一些典型测试用例：

vector<TestCase> testCases = { {23121, {2, 4, 9}, "22999", "基本测试用例"}, {5, {2, 4}, "4", "单位数测试"}, {10000, {1, 2, 3}, "3333", "10^k形式 - 需要少一位的情况"}, {555, {1, 3, 5}, "553", "数字包含在集合A的情况"}, {1000, {9}, "999", "集合A只有一个数字"}, {987654, {1, 3, 5, 7, 9}, "979999", "复杂用例 - 需要回溯多位"} };

5.2 测试框架实现

一个完整的测试框架可以帮助我们快速验证算法正确性：

void testCases() { struct TestCase { int n; vector<int> A; string expected; string description; }; vector<TestCase> testCases = { // 测试用例列表 }; int passed = 0; for (const auto& tc : testCases) { string result = findMaxNumber(tc.n, tc.A); if (result == tc.expected) { passed++; } } cout << "测试结果: " << passed << "/" << testCases.size() << " 通过" << endl; }

在面试中展示这种系统化的测试思维会给面试官留下好印象。我记得有位候选人不仅写了测试用例，还解释了每个用例的设计意图，最后获得了很高的评价。

6. 常见错误与避坑指南

6.1 数字比较的陷阱

在处理数字比较大小时，直接使用整数比较可能会遇到溢出问题。这就是为什么我们要把n转为字符串处理：

// 可能溢出 if (current_num < n) {...} // 安全做法 string n_str = to_string(n); if (path_str < n_str) {...}

特别是在处理大数时（比如n有20位），整数类型根本无法存储，字符串比较是更可靠的选择。

6.2 贪心条件的遗漏

另一个常见错误是忘记处理所有贪心条件。完整的贪心优化应该包括：

1. 前面位已小于n的情况
2. 当前位小于n对应位的情况
3. 继续递归的条件（当前位等于n对应位）

缺少任何一个条件都可能导致算法失效或效率降低。

6.3 递归终止条件

递归终止条件需要仔细设计：

1. 当路径长度等于n的长度时终止
2. 找到有效解时提前终止
3. 所有可能性都尝试后终止

不正确的终止条件可能导致无限递归或错过有效解。

7. 算法变种与扩展思考

7.1 变种问题举例

掌握了基本解法后，可以思考一些变种问题：

1. 找出大于n的最小组合数
2. 允许重复使用数字或不重复使用
3. 组合数需要满足特定数学性质（如素数、回文数等）

这些变种在面试中也很常见，考察候选人举一反三的能力。

7.2 其他算法思路

除了回溯+贪心，这道题还可以考虑其他解法：

1. 迭代法：从高位到低位逐步构建结果
2. 数学构造法：通过数学分析直接构造结果
3. 二分搜索：在所有可能的组合中进行二分查找

不过综合来看，回溯+贪心的组合在效率和实现难度上达到了较好的平衡。

7.3 实际应用场景

这类算法在实际中有广泛应用：

1. 密码破解中的组合尝试
2. 游戏中的数字谜题求解
3. 金融系统中的最优化报价
4. 自动化测试中的边界值生成

理解其核心思想可以帮助我们解决更多实际问题。