#902. 最大为 N 的数字组合

LeetCode 原题链接

#题目描述

给定按升序排列、互不相同的数字字符数组 digits 和整数 n，统计可以用 digits 中数字重复组合出的、范围在 [1, n] 内的正整数个数。

输入：digits = ["1","3","5","7"], n = 100
输出：20

长度为 1 的合法数有 4 个，长度为 2 的有 4² = 16 个；无法组成不超过 100 的三位数，所以共 20 个。

#题型判断

不能真的生成所有组合。应先按位数计数，再处理与 n 位数相同的数字：

1. 位数比 n 少的数字一定小于 n，可直接用乘法原理统计。
2. 与 n 等长时，从最高位到最低位逐位比较。

这是数位计数，也可以视作数位 DP 的简化形式。

#核心思路

设 n 有 length 位，可选数字有 digitCount 个。

#1. 统计位数更少的数字

依次枚举数字长度：

len = 1, 2, ..., length - 1

题目保证 digits 不包含 "0"，所以每一位都可以从 digitCount 个数字中任意选择。长度为 len 的数字共有：

digitCount^len

这些数字的位数少于 n，因此一定小于 n，可以全部计入答案。

#2. 统计与 n 等长的数字

从 n 的最高位开始逐位处理。进入第 position 位时，始终满足：

前 position 位已经与 n 的前缀完全相同

比较当前位时有三种选择：

• 选择小于 n 当前位的数字：整个数字已经确定小于 n，剩余位可以任意选择。
• 选择等于 n 当前位的数字：前缀继续保持相等，进入下一位比较。
• 选择大于 n 当前位的数字：整个数字一定大于 n，不能计入答案。

如果 digits 中不存在等于当前位的数字，那么所有更小的选择都已经统计，更大的选择又不合法，当前相等前缀无法继续，可以直接返回。

如果 n 的每一位都能在 digits 中找到相同数字，说明 n 本身也能组成，最后需要额外加 1。

#示例步骤

digits = ["1","3","5","7"]，n = 365：

365 是三位数。整个统计过程分成两部分：先统计一位数和两位数，再单独统计不超过 365 的三位数。

#1. 统计位数更少的数字

一位数有 4 个：

1、3、5、7

两位数的十位和个位都可以从 digits 中任意选择，所以有：

4 × 4 = 4² = 16

这些数字都不足三位，一定小于 365，因此先得到：

4 + 16 = 20

#2. 统计与 365 等长的数字

三位数必须从百位开始与 365 比较。这里要抓住一个关键点：

• 当前位比 n 的对应位小，整个数字就已经确定小于 n，后面的位可以任意选择。
• 当前位与 n 的对应位相等，还不能确定大小，需要继续比较下一位。
• 当前位比 n 的对应位大，整个数字一定大于 n，不能计入。

#比较百位

365 的百位是 3，可选数字是 1、3、5、7：

• 选择 1：百位满足 1 < 3，所以所有 1xx 都小于 365。剩余十位、个位各有 4 种选择，共有 1 × 4² = 16 个。
• 选择 3：百位与 365 相等，暂时不能计数，需要继续比较十位。
• 选择 5 或 7：百位已经大于 3，组成的数一定大于 365，不能计入。

百位选择 1 时得到的 16 个数字是：

111、113、115、117
131、133、135、137
151、153、155、157
171、173、175、177

到这里累计有：

20 + 16 = 36

#比较十位

只有百位选择 3 的分支还需要继续，也就是说当前已经匹配了前缀 3。365 的十位是 6：

• 选择 1、3、5：它们都小于 6，所以 31x、33x、35x 一定小于 365。个位可以任意选择，共有 3 × 4¹ = 12 个。
• 选择 7：十位大于 6，组成的数一定大于 365，不能计入。
• digits 中没有 6：无法让十位继续与 365 相等，因此相等分支到这里结束，不需要再比较个位。

这 12 个数字是：

311、313、315、317
331、333、335、337
351、353、355、357

最终统计结果为：

一位数：                     4
两位数：                    16
百位选择 1 的三位数：       16
百位选择 3、十位小于 6：    12
--------------------------------
总数：                      48

代码中的：

const remainingLength = target.length - position - 1;
result += digitCount ** remainingLength;

就是在计算“当前位选择得更小后，剩余位置可以任意选择”的组合数。比较百位时还剩两位，所以增加 4²；比较十位时还剩一位，所以每个更小的十位选择增加 4¹。

#代码实现

var atMostNGivenDigitSet = function (digits, n) {
  const target = String(n);
  const digitCount = digits.length;
  let result = 0;

  // 所有位数少于 n 的数字都小于 n。
  for (let length = 1; length < target.length; length++) {
    result += digitCount ** length;
  }

  // 统计与 n 等长、且不大于 n 的数字。
  for (let position = 0; position < target.length; position++) {
    let hasEqualDigit = false;

    for (const digit of digits) {
      if (digit < target[position]) {
        const remainingLength = target.length - position - 1;
        result += digitCount ** remainingLength;
      } else if (digit === target[position]) {
        hasEqualDigit = true;
      } else {
        break;
      }
    }

    if (!hasEqualDigit) {
      return result;
    }
  }

  // 每一位都匹配，n 本身也是合法组合。
  return result + 1;
};

#变式：只找到不大于 n 的最大数字

如果题目不要求统计个数，而是要求从 digits 中重复选择数字，组成一个不大于 n 的最大数字，思路会从“计数”变成“构造”。

核心策略是：尽量让结果和 n 的前缀相同；一旦某一位必须选更小的数字，后面的所有位都填 digits 中最大的数字。

处理时仍然从高位到低位比较：

1. 当前位能选择等于 n 当前位的数字，就先保持相等，继续看下一位。
2. 当前位不能相等，但存在更小的数字，就选最大的那个更小数字，后面全部填最大数字。
3. 当前位既不能相等，也没有更小数字，就需要向前回退，找到前面某一位可以变小的位置，然后后面全部填最大数字。
4. 如果前面也没有任何一位可以变小，说明无法组成与 n 等长的合法数字，只能返回位数少一位、全部由最大数字组成的数。

例如 digits = ["1","3","5","7"]，n = 365：

百位 3 可以相等，继续
十位 6 不能相等，但可以选更小的 5
个位直接填最大数字 7

得到 357

再看一个需要回退的例子，digits = ["1","3","5","7"]，n = 300：

百位 3 可以相等，继续
十位 0 没有相等数字，也没有更小数字
向前回退到百位，把 3 降成 1
剩余位全部填最大数字 7

得到 177

function largestAtMostN(digits, n) {
  const target = String(n);
  const maxDigit = digits[digits.length - 1];

  // 从第 position 位开始构造，返回字符串；构造失败返回 null。
  const build = (position) => {
    if (position === target.length) return ""; // 每一位都匹配，就是 n 本身。

    const current = target[position];

    // 1. 当前位能相等就先保持相等，递归构造后面的位。
    if (digits.includes(current)) {
      const rest = build(position + 1);
      if (rest !== null) return current + rest;
      // rest 为 null 说明后面走不通，回退到下面改选更小的数字。
    }

    // 2. 选比当前位小的最大数字，后面全部填最大数字。
    const smallerDigit = [...digits].reverse().find((digit) => digit < current);
    if (smallerDigit) {
      return smallerDigit + maxDigit.repeat(target.length - position - 1);
    }

    // 3. 既不相等也没有更小数字，本层失败，让上一层回退。
    return null;
  };

  const answer = build(0);
  if (answer !== null) return Number(answer);

  // 第一位就失败：只能返回位数少一位、全由最大数字组成的数。
  return target.length > 1
    ? Number(maxDigit.repeat(target.length - 1))
    : null;
}

这里用递归代替手动回退：build(position) 返回 null 时，调用它的上一层自然会走到“选更小数字”的分支，调用栈本身就保存了前缀，不需要额外的数组和反向循环。

这段代码返回的是数字。如果不存在任何合法正整数，例如 digits = ["5"]、n = 3，返回 null。如果担心结果超过 JavaScript 安全整数范围，可以保留字符串结果，不做 Number(...) 转换。

#复杂度与易错点

• 设 L 为 n 的位数、D 为 digits.length，时间复杂度为 O(L × D)，也就是 O(log n × digits.length)。
• 空间复杂度：O(L)，用于保存 String(n)。
• digitCount ** len 成立的前提是 digits 不包含 "0"；否则最高位不能为 0，需要单独处理前导零。
• digit 和 target[position] 都是单个数字字符，"1" 到 "9" 的字典序与数值顺序一致，因此可以直接比较。
• 处理某一位时，必须保证此前的前缀与 n 相等；一旦当前位选择了更小的数字，剩余位就可以任意组合并一次性计数。
• 当前位没有相同数字时，应立即返回，因为相等前缀已经无法继续。
• 只有完整匹配 n 的每一位时，才能把 n 本身计入。