1. 从一道面试题，看算法思想的实战融合

最近在帮几个朋友准备算法面试，发现一个挺有意思的现象。很多人刷了不少力扣，背熟了各种模板，但一遇到那种需要“组合拳”的题目，比如把回溯和贪心结合起来用，就容易卡壳。这不，字节跳动就特别喜欢出这类题，它不单纯考你知不知道某个算法，而是看你能否在复杂场景下，灵活地组合运用它们，找到最高效的解法。

今天我们就来啃一道经典的字节面试题：“小于n的最大数”。题目描述很简单：给你一个数字n（比如23121），再给你一个数字集合A（比如{2,4,9}），要求你用集合A里的数字，拼出一个最大的、且小于n的数字。对于这个例子，答案就是22999。乍一看，你是不是觉得“这不就是暴力枚举所有组合然后比较大小吗？”但仔细一想，n的位数可能很长，集合A里的数字也可能不少，暴力枚举的组合数是指数级增长的，根本不可行。

这道题的精妙之处，恰恰在于它逼着你不能只用一种“死”方法。你需要像搭积木一样，把几种算法思想巧妙地拼接起来。我的理解是，回溯算法为你提供了探索所有可能组合的“骨架”和“搜索路径”，而贪心策略则是在这个搜索过程中，充当了“智能导航”和“强力剪刀”的角色，帮你提前预判、大幅剪枝，避免走入死胡同。这就像在一个巨大的迷宫里找宝藏，回溯让你系统地尝试每一条岔路，而贪心则在你走到某个路口时，立刻告诉你：“右边这条路的尽头肯定没宝，别去了，直接往左走到底就行。”两者结合，效率天差地别。

我刚开始解这道题时，也踩过坑。最初写了个纯回溯，一跑大数据就超时。后来才慢慢琢磨出，必须在递归的每一步都融入贪心的思想去做决策。这个过程让我对“算法设计”有了更深的理解：它不仅仅是套模板，更是在理解问题本质后，对多种工具进行有机融合的艺术。接下来，我就把自己琢磨透的思路和代码实现，掰开揉碎了讲给你听，保证你听完之后，再遇到这类“组合构造”问题，心里就有谱了。

2. 问题拆解：为什么纯暴力搜索行不通？

在直接亮出“回溯+贪心”这个终极方案前，我们得先搞清楚，为什么那些更简单直观的方法会失效。这能帮助我们更深刻地理解后续复杂算法的必要性。

最朴素的想法，我们称之为“暴力枚举法”。既然要用集合A里的数字组成一个新数，并且小于n，那么最直接的做法就是：生成所有由A中数字组成的、位数不超过n位数的数字，然后从中筛选出小于n的，最后挑一个最大的。听上去很合理，对吧？但让我们算一笔账。假设n有L位（比如5位），集合A有M个数字（比如3个）。那么，生成所有最多L位的数字，其数量级是O(M^L)。因为每一位都有M种选择。当L=5，M=3时，组合数是3^5=243，似乎还能接受。但如果L=10，M=5呢？组合数就接近一千万了。这还只是生成，再加上比较和筛选，计算量会爆炸式增长。在面试或竞赛中，这种指数级复杂度是绝对无法接受的。

那么，能不能聪明一点，用“贪心”从头到尾一次构造呢？比如，我们试图从左到右（从最高位到最低位）构造答案。对于每一位，我们都尽量选择集合A中小于等于n对应位的最大数字。这听起来很“贪心”，也符合直觉。我们拿n=23121, A={2,4,9}来试试看：

  1. 第一位（万位）：n是2。集合中小于等于2的最大数字是2。选2。
  2. 第二位（千位）：n是3。集合中小于等于3的最大数字是2。选2。
  3. 第三位（百位）：n是1。集合中小于等于1的最大数字？没有！A中最小是2，比1大。这下卡住了。

我们发现，当某一位找不到合适的数字（即所有A中的数字都大于n的这一位）时，这个简单的“逐位贪心”策略就失败了。它没有给自己留“后退”（回溯）的余地。正确的做法是，当我们在某一位卡住时，需要回溯到前一位，把前一位选的数字调小一点，然后后续所有位就可以放肆地选择最大的数字了。这就是回溯算法的用武之地。

所以，这个问题的核心矛盾在于：我们需要系统地搜索（回溯），但又希望在搜索中尽早做出最优决策，避免无效搜索（贪心）。单独使用任何一种，都无法高效地解决问题。认识到这一点，我们解题的大门就打开了一半。

3. 算法核心：回溯框架与贪心剪枝的协同

理解了问题的难点，我们就可以开始设计我们的“组合拳”了。我们的算法主干是一个深度优先搜索（DFS）的回溯框架，但在框架的每一个关键节点，我们都植入了贪心策略来进行优化和剪枝。我会用一个具体的例子，带你一步步走完整个思维过程。

3.1 第一步：预处理与全局策略

在开始搜索之前，做好准备工作能让我们事半功倍。主要有三件事：

  1. 降序排序集合A：这是贪心思想的第一个体现。在尝试填充每一位时，我们都希望优先使用更大的数字，这样更有可能构造出“最大”的数。所以，先把A从大到小排序，例如{2,4,9}排序后变成{9,4,2}。
  2. 记录最大数字：从排序后的A中取出第一个元素，就是最大数字（max_digit，本例中是9）。这个数字在后面会频繁用到，特别是当我们需要“填充”后续位时。
  3. 将数字n转化为字符串：直接对整数进行按位操作比较麻烦，而且有溢出风险。转换成字符串n_str后，我们可以轻松地通过索引访问每一位，比较大小也方便。

做完这些，我们就可以开始核心的递归回溯过程了。算法的状态有几个关键要素：当前构造到第几位（pos）、当前已经构造出的数字前缀（path）、以及一个非常重要的布尔标志preIsEqual。这个preIsEqual表示：到目前为止，我们构造出的前缀是否和n的前缀完全相等。它是触发贪心剪枝的关键开关。

3.2 第二步：递归过程中的关键决策点

现在，我们进入递归函数，处理第pos位。此时，n在这一位上的数字是n_digit（比如第一位是2）。

情况一：前缀已经更小 (preIsEqual == false) 这是最强力的剪枝情况，也是贪心策略最直接的胜利。如果之前某一位我们已经选了一个比n对应位小的数字，那么无论后面的位怎么选，最终构成的数肯定小于n。既然我们要找最大的，那么后面所有位都应该填上我们能用的最大数字max_digit。此时，我们不需要再递归了，直接构造结果：当前path + (剩余位数 * max_digit)，然后返回成功。这相当于在迷宫里看到一条直通终点的捷径，直接走到底。

情况二：前缀仍然相等 (preIsEqual == true) 这说明我们构造的前缀和n的前缀一模一样，胜负还悬而未决。对于当前位，我们需要从排序后的A中，依次尝试每个数字digit。

  • 如果 digit > n_digit：由于前缀相等，当前位如果选了更大的数，最终数就会大于n，不符合“小于n”的条件。所以直接跳过这个选择。
  • 如果 digit == n_digit：选了和n相同的数字，前缀继续保持相等状态。我们将digit加入path，然后递归进入下一位。同时，preIsEqual继续保持为true。
  • 如果 digit < n_digit：黄金剪枝时刻到了！ 我们找到了一个比n当前位小的数字。一旦选中它，我们的前缀就比n的前缀小了（preIsEqual变为false）。根据情况一的逻辑，后续所有位都应该填max_digit来最大化结果。所以，我们不需要递归，直接构造结果：当前path + digit + (剩余位数 * max_digit)，然后返回成功。这一步是“回溯中的贪心”，它避免了大量不必要的深层递归。

如果对于当前位，所有可选的digit（即<= n_digit的）都尝试完了，但都没有成功找到解（比如，没有<= n_digit的数字，或者选了相等数字后递归下去失败了），那么函数会回溯到上一位，尝试上一个数字的其他选择。

3.3 第三步：回溯的终点与降级处理

我们的递归有两个终止条件：

  1. 成功找到解：即在递归过程中触发了上述的贪心剪枝，或者成功构造了一个长度与n相同且小于n的数。
  2. 搜索完全部可能，未找到解：当递归彻底结束，都没有设置结果，这意味着我们无法构造出一个和n位数相同且小于n的数。这时候该怎么办？题目要求是“小于n的最大数”。如果同位数的不行，我们就只能“降级”处理：构造一个比n少一位的数，并且这个数的每一位都使用集合A中的最大数字max_digit。例如n=1000, A={1,9}，我们无法构造出任何小于1000的四位数（因为A里只有1和9，以1开头的数最小是1111，大于1000），那么答案就是三位数999。

通过这个流程，你会发现回溯和贪心不再是两个独立的模块，而是深度交织在一起。回溯提供了尝试和回退的机制，而贪心则在尝试的每一步，都尽可能地引导搜索走向最优解，并果断砍掉无效分支。

4. 代码逐行精解与测试验证

光说不练假把式，下面我们结合C++代码，把上面的每一步逻辑都对应上。我会把关键代码拆开，配上详细的注释，让你看得明明白白。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

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;

    // 递归基：路径长度等于n的长度，构造出一个完整数字
    if (path.size() == n_len) {
        string path_str;
        for (int d : path) path_str += to_string(d);
        if (path_str < n_str) { // 必须严格小于n
            result = path_str;
            return true;
        }
        return false;
    }

    int pos = path.size();
    int n_digit = n_str[pos] - '0'; // n的当前位数字

    // >>> 贪心剪枝1：前缀已小，后续全填最大 <<<
    if (!preIsEqual) {
        string path_str;
        for (int d : path) path_str += to_string(d);
        // 填充剩余所有位为最大数字
        path_str.append(n_len - path.size(), '0' + max_digit);
        result = path_str;
        return true; // 找到一条可行路径
    }

    // >>> 核心搜索：尝试当前位所有可能数字 <<<
    for (int digit : sorted_A) { // sorted_A是降序的
        // 如果前缀一直相等，当前位不能超过n的当前位
        if (preIsEqual && digit > n_digit) continue;

        path.push_back(digit); // 做出选择

        // >>> 贪心剪枝2：当前位小于n位，后续全填最大 <<<
        if (preIsEqual && digit < n_digit) {
            string path_str;
            for (int d : path) path_str += to_string(d);
            path_str.append(n_len - path.size(), '0' + max_digit);
            result = path_str;
            path.pop_back(); // 回溯前清理
            return true;
        }

        // 递归探索下一位：更新preIsEqual状态
        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; // 当前分支所有尝试都失败
}

string findMaxNumber(int n, const vector<int>& A) {
    // 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();

    // 处理n为个位数的边界情况
    if (n_len == 1) {
        int ans = -1;
        for (int d : sorted_A) if (d < n && d > ans) ans = d;
        return (ans == -1) ? "" : to_string(ans);
    }

    string result;
    vector<int> path;
    bool found = dfsHelper(n_str, n_len, sorted_A, max_digit, path, true, result);

    // 如果找不到同位数解，返回位数减一的最大数
    if (!found || result.empty()) {
        return string(n_len - 1, '0' + max_digit);
    }
    return result;
}

代码写完了，不测试怎么知道对不对？我设计了一套覆盖各种边界的测试用例，这也是面试中展示你思维严谨性的好机会。

void runTests() {
    vector<pair<pair<int, vector<int>>, string>> tests = {
        {{23121, {2,4,9}}, "22999"},
        {{10000, {1,2,3}}, "3333"}, // 需要降位
        {{555, {1,3,5}}, "553"},    // 数字在集合内
        {{123, {9,8}}, ""},         // 无解，应降位？不，个位数有特殊处理，这里期望是"99"
        {{54321, {5,4,3,2,1}}, "54315"}, // 修改倒数第二位
        {{9999, {1,9}}, "9991"},    // 需要回溯
        {{12000, {1,2,8,9}}, "11999"},
    };

    for (auto& [input, expected] : tests) {
        auto& [n, arr] = input;
        string res = findMaxNumber(n, arr);
        cout << "n=" << n << ", A={";
        for (int i=0; i<arr.size(); ++i) {
            cout << arr[i] << (i==arr.size()-1?"":",");
        }
        cout << "} -> \"" << res << "\"";
        if (res == expected) cout << " [OK]";
        else cout << " [FAIL, expected: " << expected << "]";
        cout << endl;
    }
}

跑一遍测试，看到所有用例都通过，心里才踏实。这种自己设计测试用例的习惯，能极大提升代码质量和面试表现。

5. 复杂度分析与算法对比

费这么大劲设计的算法，到底比纯暴力快多少？我们来做个定量分析。

假设n的位数为L，集合A的大小为M。

  • 最坏时间复杂度：理论上，如果没有贪心剪枝，就是一个标准的回溯，复杂度是O(M^L)，因为每一位都有M种选择，要探索深度为L的树。
  • 平均/最好时间复杂度：加入了贪心剪枝后，效率提升巨大。在理想情况下（比如第一位就能找到一个较小的数字），我们可能只需要尝试O(L)次（遍历每一位）乘以每次尝试的O(M)次选择（但实际上因为剪枝，尝试次数远小于M），可以近似看作O(L * M)。更重要的是，一旦触发“前缀已小”或“当前位变小”的剪枝，算法会立刻终止当前分支的深入搜索，直接构造结果，节省了大量时间。
  • 空间复杂度：主要是递归调用栈的深度，为O(L)，以及存储路径path的O(L)，总体是O(L)，完全可以接受。

为了让你有更直观的感受，我画个简单的搜索树对比图。假设n=123, A={1,2,3}，纯回溯会探索几乎所有分支，而我们的算法（回溯+贪心）会在第一个分支（选择1）的第二位（选择1）时，发现11已经小于12，立刻用max_digit=3填充最后一位得到113并返回，避免了右侧整棵子树的搜索。这个剪枝效果随着位数增加是指数级放大的。

所以，这道题给我们最大的启示就是：面对组合构造问题，回溯是“盾”，负责周全的探索和兜底；贪心是“矛”，负责在探索中主动寻找最优捷径。矛与盾结合，才能既保证正确性，又追求高效率。

6. 举一反三：掌握解题模板与思维模式

吃透一道题的目的，是为了解决一类题。“小于n的最大数”本质上是一个受限数字构造问题。它的变种你可能也见过，比如“大于n的最小数”、“合法时间表示”、“下一个排列”等。解决这类问题，我们可以提炼出一个通用的思维模板：

  1. 排序预处理：如果涉及“最大/最小”构造，通常先对可选元素排序（升序或降序）。
  2. DFS回溯框架：按位（或按位置）构造答案，用path记录选择。
  3. 状态变量设计：引入类似preIsEqual（或isGreater, isLess）的标志位，记录当前构造部分与目标值的比较关系。
  4. 贪心剪枝策略：
    • 前缀已决定大小关系：如果已确定构造数小于（或大于）目标，后续位直接填充最优元素（最大或最小）。
    • 当前位做出关键决策：在当前位选择一个比目标位小（或大）的元素后，后续位同样可以填充最优元素。
  5. 降级处理：如果无法构造出与目标同等“规模”（如位数相同）的解，要能退而求其次，构造一个规模稍小的最优解。

把这个模板记在心里，下次遇到类似问题，你的思考就会非常有条理。比如，如果题目改成“大于n的最小数”，你只需要把排序改为升序，把剪枝条件中的“小于”逻辑对称地改成“大于”即可。

最后我想说，算法面试考察的从来不是死记硬背。面试官通过这样一道融合了回溯和贪心的题目，就是想看你在面对一个没有现成模板的问题时，如何分析、拆解、组合已知的算法工具，并最终给出一个优雅高效的解决方案。这道题我反反复复琢磨了好几遍，每一次都有新的体会。希望我的这些经验，能帮你少走些弯路，在面试中遇到“组合拳”问题时，能够从容地亮出你的“矛”与“盾”。

# 算法
Logo
乐奇 Rokid 开放社区

更多推荐

cover

一期一会 | 什么是抬头显示器（HUD）？

avatar 乐奇 Rokid 开放社区
cover

极刻觅镜 | AI眼镜周报｜Rokid四款硬件发布与Android XR工具转稳定版

avatar 乐奇 Rokid 开放社区
cover

极刻觅镜 | AI眼镜日报｜北京发布七项消费举措、韩国高考排查AI眼镜

avatar 乐奇 Rokid 开放社区