基于二进制字符串的指定规则组合生成算法实现求助

需求说明 #

要实现一个算法，生成满足以下规则的二进制字符串组合：

• 输入的二进制字符串里，0全是成对的（也就是只有"00"，没有单独的0）；
• 输出的字符串里，0也必须全是成对的；
• 组合只能通过把输入里的'1'替换成'00'得到（输入里的"00"不能改成'1'）。

举个例子：

输入：11
输出：11、001、100、0000
注意：010这种输出是不允许的，因为里面的0不成对。

你的代码问题分析 #

你写的代码有几个核心问题：

1. 索引错位：把'1'替换成'00'后，字符串长度会增加1，但内层循环的j没做调整，后续字符的索引直接乱掉，没法正确处理多次替换操作；
2. 缺少多轮替换逻辑：代码只在原字符串基础上做单次替换，没有递归或迭代处理替换后的新字符串，所以生成不了多个'1'同时被替换的结果（比如输入11时的0000就漏掉了）；
3. 逻辑漏洞：嵌套循环的写法会导致部分组合重复生成，部分组合被遗漏，处理长字符串比如1111时完全出错。

正确实现方案 #

核心思路是逐个遍历输入的每个字符，对每个'1'做两种选择：要么保留，要么换成'00'；对于输入里的"00"，直接跳过两个字符就行，因为输入本身保证0是成对的，不用动它们。

用递归回溯的方式实现最直观，代码如下：

#include <iostream>
#include <set>
#include <string>

void generateCombinations(const std::string& input, int index, std::string current, std::set<std::string>& result) {
    // 遍历到字符串末尾，把当前组合加入结果
    if (index >= input.length()) {
        result.insert(current);
        return;
    }

    if (input[index] == '1') {
        // 选择1：保留当前的'1'，继续处理下一个字符
        generateCombinations(input, index + 1, current + '1', result);
        // 选择2：把'1'换成'00'，继续处理下一个字符
        generateCombinations(input, index + 1, current + "00", result);
    } else if (input[index] == '0') {
        // 输入里的0都是成对的，直接加"00"，然后跳过下一个0
        current += "00";
        generateCombinations(input, index + 2, current, result);
    }
}

void get_combinations(const std::string& bin, std::set<std::string>& result) {
    result.clear();
    generateCombinations(bin, 0, "", result);
}

// 测试用例
int main() {
    std::set<std::string> result;
    get_combinations("11", result);
    for (const auto& s : result) {
        std::cout << s << std::endl;
    }
    return 0;
}

代码说明

• 递归终止条件：当遍历到输入字符串的末尾时，把当前构建好的字符串加入结果集；
• 处理'1'：给每个'1'提供两个分支，分别对应保留或替换为'00'，继续递归处理下一个字符；
• 处理'0'：因为输入保证0是成对的，直接添加"00"并跳过下一个字符，避免拆分已有0对；
• 用set去重：虽然逻辑上不会生成重复组合，但set能确保结果集中没有重复项。

测试输入11时，会生成所有4种符合要求的组合；处理1111这类长字符串时，也能正确生成所有2^4=16种组合（每个'1'都有两种选择）。

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