c++ - 在 C++ 中计算具有不同列数的数字的不同组合？

Question

如果有人能指出我解决这个问题的正确方向，我将不胜感激。我试图找到各种数字的所有不同组合，每个数字都有不同的列数(在 C++ 中)。例如考虑数字 2:

两列:

2 = { 2 , 0 } { 0 , 2 } { 1 , 1 }

三列:

2 = { 0 , 0 , 2 } { 0 , 2 , 0 } { 2 , 0 , 0 } { 1 , 1 , 0 } { 0 , 1 , 1 } { 1 , 0 , 1 }

四列:

2 = { 0 , 0 , 0 , 2 } { 0 , 0 , 2 , 0 } { 0 , 2 , 0 , 0 } { 2 , 0 , 0 , 0 } { 1 , 1 , 0 , 0 } { 0 , 0 , 1 , 1 } { 0 , 1 , 1 , 0 } { 1 , 0 , 0 , 1 } { 1 , 0 , 1 , 0 } { 0 , 1 , 0 , 1 }

提前致谢!

Answer 1

这是我的尝试:

void combinations(int n, int columns, std::vector<int>& soFar)
{
    if (columns == 1)
    {
        for (auto e : soFar)
            std::cout << e << " ";
        std::cout << n << '\n';
        return;
    }

    for (int i = 0; i <= n; ++i)
    {
        soFar.push_back(i);
        combinations(n - i, columns - 1, soFar);
        soFar.pop_back();
    }
}

void combinations(int n, int columns)
{
    std::vector<int> soFar;
    combinations(n, columns, soFar);
}

基本上，您一直将数字分成两个子部分，直到达到深度限制(您的情况下的列数)。
为了在备份过程中继续打印之前的数字，我将它们存储在 soFar vector 中，并相应地推送和弹出它们。

这是 combinations(2, 4) 的输出:

0 0 0 2
0 0 1 1
0 0 2 0
0 1 0 1
0 1 1 0
0 2 0 0
1 0 0 1
1 0 1 0
1 1 0 0
2 0 0 0