Algorithm to print all solutions of equation

Question

I have this problem:

Assume that we have this simple equation

x1 + x2 + x3 + x4 + x5 = 20

and I want to print all non-negative integer solutions of this equation and i must use only numbers 3, 4, 5, 6

for example:

0 + 4 + 4 + 6 + 6 = 20
etc.

I dont want write it in specific programming language, only in pseudo-code

Any idea?

There are infinite number of solutions to that equation. Do you mean you want to print all non-negative integer solutions? — JJJ, Oct 18 '15 at 09:45
do you want to eliminate duplicates? for e.g. `15 + 1 + 2 + 1 + 1` and `15 + 1 + 1 + 2 + 1` will one value be eliminated or both kept — , Oct 18 '15 at 09:48

score 0 · Answer 1 · edited May 23 '17 at 12:03

0

This might work: Finding all possible combinations of numbers to reach a given sum

You can start the set of numbers as [3,4,5,6] and not to remove the element once chosen and check by the depth of recursion if you got exactly the needed number of elements.

This is more generic and will allow to resolve equations with different number of elements without the need to add/remove nested loops.

edited May 23 '17 at 12:03

Community

1
1

answered Oct 18 '15 at 09:59

Roman Pustylnikov

1,937
1
10
18

Then you cannot use 0 and all the solutions are non-negative by definition. – Roman Pustylnikov Oct 18 '15 at 10:20

score 0 · Accepted Answer · answered Oct 18 '15 at 14:41

In java code

    int []numbers = {0, 3, 4, 5, 6};
    int res=20;
    int sum=0;

    for(int i:numbers)
        for(int j:numbers)
            for(int k:numbers)
                for(int l:numbers)
                    for(int m:numbers) {
                        sum = i + j + k + l + m;
                        if(sum==res) {
                        String solution = i + " " + j + " " + k + " " + l +" " + m;
                        Log.i("solution", "---- " + solution);}
                    }

In pseudo code is something like this:

FOR each number1 in the number_list
    FOR each number2 in the number_list
        FOR each number3 in the number_list
            FOR each number4 in the number_list
                FOR each number5 in the number_list
                    sum = number1+number2+number3+number4+number5;
                    IF sum IS EQUAL TO 20 THEN
                        Print number1, number2, number3, number4, number5
                    ENDIF
                ENDFOR
            ENDFOR
        ENDFOR
    ENDFOR
ENDFOR

Algorithm to print all solutions of equation

2 Answers2