c++ - 将所有组合放入数组中，其中所有条目的总和等于给定整数

Question

我试图在给定的固定大小的数组中获取所有可能的组合，其中所有条目的总和等于给定的整数。
例:
给定整数n:5和给定数组大小= 4
{0,0,0,5}
{0,0,5,0}
...
{0,0,1,4}
...
{1,1,1,2}
...
我的目标是获取这些组合并将其保存在C++ vector 中。
我希望你能帮助我。

Answer 1

简单的递归方法:

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> v;
vector<int> parts;

void partitions(int sum, int k) {
    if (k == 1) {
        parts[k - 1] = sum;
        v.push_back(parts);
        return;
    }
    for (int i = 0; i <= sum; i++) {
        parts[k-1] = i;
        partitions(sum - i, k - 1);
    }
}

int main()
{
    int k = 3;
    int sum = 5;
    for (int i = 0; i < k; i++)
        parts.push_back(0);
    partitions(sum, k);

    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++)
            cout << v[i][j] << " ";
        cout << endl;
    }
    return 0;
}

5 0 0
4 1 0
3 2 0
2 3 0
1 4 0
0 5 0
4 0 1
3 1 1
2 2 1
1 3 1
0 4 1
3 0 2
2 1 2
1 2 2
0 3 2
2 0 3
1 1 3
0 2 3
1 0 4
0 1 4
0 0 5