本文介绍一种基于斐波那契递推关系的高效递归算法，将原 o(2ⁿ·n) 的暴力枚举优化至理论最优 o(n·φⁿ)（φ≈1.618），精准生成所有不含三位及以上连续数字的合法逗号分隔字符串。
本文介绍一种基于斐波那契递推关系的高效递归算法，将原 o(2ⁿ·n) 的暴力枚举优化至理论最优 o(n·φⁿ)（φ≈1.618），精准生成所有不含三位及以上连续数字的合法逗号分隔字符串。
原始实现通过枚举全部 2n−1 种逗号插入模式（用位掩码模拟），再逐个正则过滤含 ≥3 位连续数字的非法项，导致时间复杂度高达 O(2n·n)，在输入长度 n > 20 时即不可行。但关键洞察在于：问题本质不是“枚举后过滤”，而是“构造即合法”——每一步仅允许截取长度为 1 或 2 的前缀作为独立数字段，后续递归处理剩余子串。这天然规避了三位数出现的可能，无需事后校验。
该构造过程满足清晰的递推关系：设 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 位）
这正是斐波那契数列，故输出规模为 Θ(φn)，其中 φ = (1+√5)/2 ≈ 1.618。由于每个结果平均长度为 O(n)，总字符量为 O(n·φn)，因此 O(n·φn) 是该问题的时间复杂度下界，新算法已达理论最优。
以下是优化后的递归实现（含记忆化避免重复计算）：
import java.util.*;
public static List<string> getCommaSeparatedNumbers(String num) {
Map<integer list>> memo = new HashMap();
return helper(num, 0, num.length(), memo);
}
private static List<string> helper(String num, int start, int end, Map<integer list>> memo) {
int len = end - start;
if (len == 0) return Collections.emptyList();
if (memo.containsKey(len)) return memo.get(len);
List<string> results = new ArrayList();
if (len == 1) {
results.add(num.substring(start, end));
} else if (len == 2) {
results.add(num.substring(start, end)); // "12"
results.add(num.substring(start, start + 1) + "," +
num.substring(start + 1, end)); // "1,2"
} else {
// 首段取 2 位：如 "12" + "," + 递归处理 "345..."
for (String rest : helper(num, start + 2, end, memo)) {
results.add(num.substring(start, start + 2) + "," + rest);
}
// 首段取 1 位：如 "1" + "," + 递归处理 "234..."
for (String rest : helper(num, start + 1, end, memo)) {
results.add(num.substring(start, start + 1) + "," + rest);
}
}
memo.put(len, results);
return results;
}</string></integer></string></integer></string>
关键优势与注意事项：
- ✅ 零过滤开销：严格按 1/2 位分段，结果天然合法；
- ✅ 记忆化剪枝：memo 按子串长度缓存，避免相同长度子问题重复求解，将时间从指数级重复降为 O(n·φn)；
- ⚠️ 空间注意：递归深度为 O(n)，且需存储 O(φn) 个字符串，大输入时建议配合流式处理或迭代改写；
- ? 可扩展性：若约束改为“最多 k 位连续数字”，只需将递推改为 f(n) = f(n−1) + … + f(n−k)，算法框架不变。
综上，该解法通过问题建模重构（从“枚举-过滤”转向“递推构造”），结合数学归纳与动态规划思想，在保证正确性的同时逼近理论性能极限，是典型“理解问题本质优于优化代码细节”的范例。
