CODEWITHSUNDEEP
c++algorithm
Stefan Berger
Stefan Berger

Reputation: 17

Getting all combinations inside an array, where the sum of all entries is equal to a given integer

I am trying to get all possible combinations inside an array with a given fixed size where the sum of all entries is equal to a given integer. Example:

given integer n: 5 and given array size = 4

{0,0,0,5} {0,0,5,0} ... {0,0,1,4} ... {1,1,1,2} ...

my goal is to get those combinations and save them inside a C++ vector. I hope you can help me.

Upvotes: 1

Views: 329

Answers (1)

MBo
MBo

Reputation: 80187

Simple recursive approach:

#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

Upvotes: 1

Related Questions