Finding all possible addition and combination given a fixed number in c ( given a sum, find the possible addition and permutation of it.)

Question

I'm looking for all the possible combination of number and the permutation of them in a fixed size of array. For example, I have the total number of 5 the desired output will be

5 0 0 0

0 5 0 0

0 0 5 0

0 0 0 5

4 1 0 0

1 4 0 0

1 0 4 0

1 0 0 4

0 1 4 0

and so on... is this possible ?

Should 3 number combinations, like `2 2 1 0`, be acounted too? — GMachado, Sep 05 '18 at 03:01
If you just want to count the number of combinations, you can do a DP where your DP array is defined as `dp[i][j] = number of ways to sum to j using i numbers`. If you want to print all the combinations, use a recursive DFS as shown in pfctgeorge's answer. — eesiraed, Sep 05 '18 at 04:10
These are called [integer compositions](https://en.wikipedia.org/wiki/Composition_(combinatorics)) which is related to integer partitions, only order matters. — Joseph Wood, Sep 05 '18 at 15:28

pfctgeorge · Answer 1 · 2018-09-05T02:59:48.507

0

Use recursion:

void find(int remain, int depth, vector<int> v) {
    if (depth == 4) {
        if (remain == 0){
            for (int i = 0 ;i < 4; i++) {
                cout << v[i];
            }
            cout<<endl;
        }
        return;
    }
    for (int i = 0; i <= remain; i++) {
        v.push_back(i);
        find(remain-i, depth+1, v);
        v.pop_back();
    }
}

edited Sep 05 '18 at 02:59

answered Sep 05 '18 at 02:54

pfctgeorge

698
3
9

2

You could pass the vector by reference so you don't copy the whole thing every time you call the function. – eesiraed Sep 05 '18 at 04:09
Yeah, good advice. But since I'm not very familiar with c++, I just use a brute solution to give some hint. – pfctgeorge Sep 05 '18 at 04:57
3

This solution is inefficient. :O – KaiserKatze Sep 05 '18 at 05:06
Also, there is only one possibility for the last number, so you don't need to loop over that. – eesiraed Sep 05 '18 at 22:35

Finding all possible addition and combination given a fixed number in c ( given a sum, find the possible addition and permutation of it.)

1 Answers1