字符串二进制组合

Question

有没有一种简单的方法可以找到所有数字加起来为x点的二进制字符串，假设所有1值2分，所有0值1分。让我解释一下：

考虑到我收到一个数字 5，我怎样才能得到所有可能的字符串，例如 2*（个数）+ 1*zeros = 5。 5 次的所有结果：

00000

10000

0100

0010

0001

101

110

011

（我知道可能解的个数是5+1（x+1）的斐波那契数，但我想不出找到所有值的方法）。

我正在考虑以二进制形式添加数字或者使用基本转换器，但我可能在这里遗漏了一些东西。提前谢谢你。

Answer 1

通过一个循环，您可以生成基本字符串（在您的情况下为“00000”、“0001”和“011”），然后使用 std::next_permutation():

for( int zeros = n; zeros >= 0; zeros -= 2 ) {
    int ones = ( n - zeros ) / 2;
    std::string base = std::string( zeros, '0' ) + std::string( ones, '1' );
}

live example

Answer 2

试试这样：

#include <iostream>
#include <string>
#include <vector>

void getSums(int sum, std::vector<std::string>& results, std::string currSum) {
    if (0 == sum) {
        results.emplace_back(currSum.c_str());
        return;
    } else if (sum < 0) {
        return;
    } else {
        getSums(sum-2, results, currSum+"1");
        getSums(sum-1, results, currSum+"0");
    }
}

std::vector<std::string> getAllSums(int sum) {
    std::vector<std::string> results;
    std::string currSum;
    getSums(sum, results, currSum);
    return results;
}

int main() {
    std::vector<std::string> res = getAllSums(5);
    for (std::string& r : res) {
        std::cout << r << std::endl;
    }

}

或者切换到 DP 并缓存结果。

字符串二进制组合

String binary combinatorics

c++

string

binary

combinatorics