C++ 破解数字切割求和结果数量之谜：输入 123 竟有 4 种可能！

以下是使用 C++ 实现的代码： ```cpp #include <iostream> #include <set> #include <string> // 递归函数，用于生成所有可能的切割方式并计算求和结果 void splitAndSum(const std::string& num, int start, long long currentSum, std::set<long long>& results) { if (start == num.length()) { results.insert(currentSum); return; } long long currentNum = 0; for (int i = start; i < num.length(); ++i) { currentNum = currentNum * 10 + (num[i] - '0'); splitAndSum(num, i + 1, currentSum + currentNum, results); } } int main() { std::string n; std::cin >> n; std::set<long long> results; splitAndSum(n, 0, 0, results); std::cout << results.size() << std::endl; return 0; } ``` 代码解释： 1. `splitAndSum` 函数： - 这是一个递归函数，用于生成所有可能的切割方式并计算求和结果。 - `num` 是输入的数字字符串，`start` 表示当前切割的起始位置，`currentSum` 表示当前已经切割部分的和，`results` 是一个 `std::set`，用于存储所有不同的求和结果。 - 当 `start` 等于 `num` 的长度时，说明已经完成了一次切割，将当前的 `currentSum` 插入到 `results` 中。 - 否则，从 `start` 位置开始，依次截取不同长度的数字，将其转换为整数并累加到 `currentSum` 中，然后递归调用 `splitAndSum` 函数处理剩余的部分。 2. `main` 函数： - 读取输入的数字字符串 `n`。 - 创建一个 `std::set` 用于存储所有不同的求和结果。 - 调用 `splitAndSum` 函数生成所有可能的切割方式并计算求和结果。 - 输出 `results` 的大小，即不同求和结果的数量。 复杂度分析： - 时间复杂度：由于每个数字都有两种选择：要么作为当前数字的一部分，要么作为下一个数字的开始，因此时间复杂度为 $O(2^m)$，其中 $m$ 是输入数字的位数。 - 空间复杂度：主要用于存储所有不同的求和结果，空间复杂度为 $O(2^m)$。 ######[AI问答 | 601点数解答 | 2026-02-07 18:18:51]