Tamir Shklaz - 1 year ago 63

Java Question

Given a list of numbers

Eg:

1, 2, 3.

Get every combination of these numbers using the operations of multiplication or addition (*/+)

So in the above example the combinations would be

1+2+3

1+2*3

1*2*3

1*2+3

Ive written a basic recursive method to solve it, the way I thought about it was as follows

Given a number I can either

- Add the next number
- Multiply the next number

`START NUMBER`

/ \

* +

/ \ / \

* + * +

Etc...

But the output outputs every answer twice

The output I get when using 1,2,3 is

1*2+3

1*2+3

1*2*3

1*2*3

1+2+3

1+2+3

1+2*3

1+2*3

- Is this an acceptable algorithm and if so what is going wrong with my code
- Is there another more efficient way of doing this.

`package AG;`

import java.util.LinkedList;

import java.util.Stack;

/**

*

* @author Tamir Shklaz

*/

public class ArithmeticGame {

/**

* @param args the command line arguments

*/

public static void main(String[] args) {

LinkedList<Integer> numbers = new LinkedList<>();

LinkedList<Integer> number = new LinkedList<>();

for (int i = 1; i <= 3; i++) {

numbers.add(i);

}

permutateSigns('*', numbers, 0, "");

permutateSigns('+', numbers, 0, "");

}

public static void permutateSigns(char operation, LinkedList<Integer> number, int pos, String expresion) {

double sum = 0;

if (pos == number.size()-1) {

expresion += number.get(pos);

System.out.println(expresion);

} else {

expresion += (Integer.toString(number.get(pos)) + Character.toString(operation));

permutateSigns('+', number, pos + 1, expresion);

permutateSigns('*', number, pos + 1, expresion);

}

}

}

Answer Source

I think your mistake is that you pass a single operator to the function permutateSigns instead of giving all operators.

Therefore you call the same function twice at the beginning, which results in doubled answers.

Here is the corrected code (I think it is what you need)

```
public class ArithmeticGame {
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
for (int i = 1; i <= 3; i++) {
numbers.add(i);
}
char[] operations = { '*', '+' };
permutateSigns(operations, numbers, 0, "");
}
public static void permutateSigns(char[] operations, LinkedList<Integer> numbers, int pos, String expression) {
expression += numbers.get(pos);
if (pos == numbers.size() - 1) {
System.out.println(expression);
} else {
for (char operation : operations) {
permutateSigns(operations, numbers, pos + 1, expression + operation);
}
}
}
}
```

Additionally, I would advise you to use **ArrayList** instead of **LinkedList**, because **get** operations which are performed will have **O(1)** time instead of **O(n)**