本文介绍一种基于斐波那契递推关系的高效递归算法，将原暴力枚举 o(2ⁿ·n) 的时间复杂度降至理论最优的 o(n·φⁿ)（φ≈1.618），并避免生成非法三位及以上连续数字的中间结果。
本文介绍一种基于斐波那契递推关系的高效递归算法，将原暴力枚举 o(2ⁿ·n) 的时间复杂度降至理论最优的 o(n·φⁿ)（φ≈1.618），并避免生成非法三位及以上连续数字的中间结果。
原始实现通过枚举所有 2n−1 种逗号插入位置（用位掩码模拟），再正则过滤含 ≥3 位连续数字的字符串，导致时间复杂度高达 O(2ⁿ·n)，在输入长度 n > 20 时即明显卡顿。但关键洞察在于：合法分割方案数本身遵循斐波那契规律——因为每个分割点仅允许在第 1 位后或第 2 位后插入首个逗号（否则会产生 ≥3 位数字），后续子问题自然递归分解。
设 f(n) 表示长度为 n 的数字字符串的合法分割方案总数，则有：
- f(1) = 1（仅 "1"）
- f(2) = 2（"12", "1,2"）
- f(n) = f(n−1) + f(n−2)（首段取 1 位 → 剩余 n−1 位；首段取 2 位 → 剩余 n−2 位）
该递推式正是斐波那契数列，其闭式解为 f(n) = Θ(φⁿ)，其中 φ = (1+√5)/2 ≈ 1.618。由于最终输出字符串总长度约为 n·f(n)（每种方案平均含 ~n/2 个字符），O(n·φⁿ) 是该问题的理论下界——任何正确算法至少需花费此时间构造全部输出。
以下为优化后的递归实现（带记忆化可进一步提升实际性能）：
public static List<string> getCommaSeparatedNumbers(String num) {
List<string> results = new ArrayList();
int n = num.length();
if (n == 0) return results;
if (n == 1) {
results.add(num);
return results;
}
if (n == 2) {
results.add(num); // "12"
results.add(num.substring(0, 1) + "," + num.substring(1)); // "1,2"
return results;
}
// 首段取前2位："12" + "," + 后续所有合法分割（对num.substring(2)递归）
for (String suffix : getCommaSeparatedNumbers(num.substring(2))) {
results.add(num.substring(0, 2) + "," + suffix);
}
// 首段取前1位："1" + "," + 后续所有合法分割（对num.substring(1)递归）
for (String suffix : getCommaSeparatedNumbers(num.substring(1))) {
results.add(num.substring(0, 1) + "," + suffix);
}
return results;
}</string></string>
✅ 优势说明：
- 零无效生成：只构造合法结构（首段长度恒为 1 或 2），彻底规避 matches(".*\d{3,}.*") 的扫描开销；
- 复杂度精准匹配下界：时间复杂度 O(n·φⁿ)，空间复杂度 O(φⁿ)（递归栈深 O(n)，每层输出 O(φⁿ) 字符）；
- 逻辑清晰可扩展：若约束改为“最多 k 位连续数字”，只需将递归分支扩展为 k 种首段长度（1 至 k 位），递推式变为 f(n) = f(n−1)+…+f(n−k)。
⚠️ 注意事项：
- 当 n ≥ 45 时，f(n) 超过 Integer.MAX_VALUE（约 10⁹），需用 long 或 BigInteger 存储计数，但实际输出列表仍受限于内存；
- 若仅需方案数而非具体字符串，可改用迭代动态规划，将空间优化至 O(1)；
- 生产环境建议添加记忆化（Map
> memo）避免重复子问题计算，尤其当输入含大量重复子串时。
该方案不仅显著提升性能，更揭示了组合问题中“结构约束→递推关系→最优算法”的典型解决路径。
