如何在C++中生成数字字符串的所有固定顺序拆分组合？

嘿，这个需求其实挺典型的——本质上就是在字符串的每一对相邻字符之间做「拆或不拆」的选择，总共有 (2^{n-1}) 种组合（n是字符串的长度），比如你给的"12479"有4个相邻位置，所以会生成16种不同的拆分结果。用回溯法是实现这个需求最直观的方式，我给你一步步拆解实现思路和代码：

实现核心思路 #

我们可以用递归回溯的方式遍历所有可能的拆分点：

• 从字符串的起始位置开始，每次选择截取一段连续子串（从当前位置到某个结束位置），把这段子串转成数字加入当前正在构建的组合
• 递归处理剩下的子串，直到处理完整个字符串，就得到了一个完整的拆分组合
• 回溯的时候把最后加入的元素移除，尝试下一种拆分方式

完整代码示例 #

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib> // 用于stoi转换

using namespace std;

// 回溯核心函数
void backtrack(const string& s, int start, vector<int>& current, vector<vector<int>>& result) {
    // 递归终止：已经处理完整个字符串，把当前组合存入结果
    if (start == s.size()) {
        result.push_back(current);
        return;
    }

    // 遍历从start开始的所有可能子串结束位置
    for (int i = start; i < s.size(); ++i) {
        // 截取[start, i]区间的子串
        string sub_str = s.substr(start, i - start + 1);
        // 转成整数（如果要处理超大数字，直接存string即可，去掉stoi）
        int num = stoi(sub_str);
        // 加入当前组合
        current.push_back(num);
        // 递归处理剩余部分
        backtrack(s, i + 1, current, result);
        // 回溯：移除最后加入的元素，尝试下一种拆分
        current.pop_back();
    }
}

// 对外暴露的调用函数
vector<vector<int>> splitNumberString(const string& data) {
    vector<vector<int>> result;
    vector<int> current_comb;
    backtrack(data, 0, current_comb, result);
    return result;
}

// 测试用例
int main() {
    string input = "12479";
    vector<vector<int>> all_combs = splitNumberString(input);

    // 打印所有组合
    for (const auto& comb : all_combs) {
        cout << "[";
        for (size_t j = 0; j < comb.size(); ++j) {
            if (j != 0) cout << ", ";
            cout << comb[j];
        }
        cout << "]" << endl;
    }

    return 0;
}

关键细节说明 #

1. 大数适配：如果输入的字符串很长（比如超过int的范围），只需要把vector<int>改成vector<string>，去掉stoi转换逻辑，直接存储子串即可，这样就不会有溢出问题。
2. 时间复杂度：总共有(2^{{n-1})种组合，每个组合的构建需要(O(n))的时间，整体时间复杂度是(O(n*2}n))，对于短字符串（长度≤20）完全够用。
3. 输出示例：运行代码后，会输出你期望的所有组合，比如[1,2,479]、[12,4,79]、[12479]等等。

内容的提问来源于stack exchange，提问作者Sahak 12