如何找出所有满足最大“阶”限制的整数组合

问题描述 #

给定整数集合 [k₀, k₁, ..., kₙ]，定义“阶”为所有元素绝对值的总和：|k₀| + |k₁| + ... + |kₙ|。已知最大阶 m_max，需要找出所有阶严格小于 m_max 的整数组合。

我的尝试：暴力遍历法 #

最开始我想到的是，每个 kᵢ 的取值范围是 -m_max 到 m_max，所以直接遍历所有可能的组合，再筛选出阶符合要求的。具体来说，这相当于把每个组合转换成 (2m_max + 1) 进制数，再映射到十进制数来完成遍历。

举个例子，当 n=2（也就是3个元素）、m_max=2 时，不考虑阶限制的组合总共有 5³=125 种，对应十进制范围 0 到 124：

(-2, -2, -2) 阶=6 → 不符合 → 对应5进制的000
(-1, -2, -2) 阶=5 → 不符合 → 对应5进制的001
(0, -2, -2) 阶=4 → 不符合 → 对应5进制的002
...
(2, 2, 2) 阶=6 → 不符合

这种方法逻辑简单，但计算量实在太大——尤其是当 n 或者 m_max 较大时，会生成大量无效组合（阶超过限制的），完全是在浪费计算资源。

更高效的生成思路 #

既然目标是生成阶严格小于 m_max 的组合，不如换个思路：先生成绝对值和满足条件的非负组合，再给每个元素补充正负号（注意0没有正负之分），这样能从源头避免无效组合的生成。

具体可以分成两步：

1. 生成非负整数组合 (a₀, a₁, ..., aₙ)，满足 a₀ + a₁ + ... + aₙ < m_max
   这一步用递归或动态规划的方式生成更高效：从第一个元素开始，a₀ 可以取 0 到 m_max-1；对于每个确定的 a₀，a₁ 可以取 0 到 (m_max-1)-a₀；以此类推，直到最后一个元素 aₙ 取 0 到剩余的数值。这样生成的非负组合天然满足和的限制，不会有无效项。
2. 为每个非负组合生成所有可能的正负变体
   针对非负组合里的每个元素：
   • 如果 aᵢ = 0，对应的 kᵢ 只能是 0；
   • 如果 aᵢ > 0，对应的 kᵢ 可以是 aᵢ 或者 -aᵢ。
     所以每个非负组合能生成 2^t 个不同的整数组合，其中 t 是组合中正数元素的个数。

比如还是 n=2、m_max=2 的例子，第一步生成的非负组合包括：

• 和为0：(0,0,0) → 只能生成1个组合(0,0,0)
• 和为1：(1,0,0)、(0,1,0)、(0,0,1) → 每个生成2个组合，比如(1,0,0)可以变成(1,0,0)和(-1,0,0)
  最终有效组合只有 1 + 3×2 =7 个，比暴力遍历的125种少了太多！

总结 #

相比暴力遍历所有组合再筛选，先生成符合和限制的非负组合、再扩展正负变体的方法，能大幅减少计算量，尤其是当 m_max 和 n 较大时，效率提升会非常显著。

备注：内容来源于stack exchange，提问作者Christ Liu