0

I found a lot of post quite similar (referring to the Coin changing Problem) but only using the sum operator. Now imagine you can add, subtract, multiply and divide, is there a way to get all the calculation combinations to a given number? Ideally in Java

Example: Given 1 5 2 4 9 try to get 16

Solutions:

  • 9+1+4+2=16
  • 2*9-(5-4+1)=16
  • 5*(4+1)-9=16
  • and so on (I found 20 of those).

Thanks.

user1902585
  • 19
  • 2
  • 1
    Do you really only want the answer to "is there a way to get all the calculation combinations to a given number?" – hatchet - done with SOverflow Dec 13 '12 at 23:53
  • 3
    What have you tried yourself, except of writing down combinations on paper? You could start with trying to figure out an algorithm to determine these combinations. – Styxxy Dec 14 '12 at 00:03

1 Answers1

4

Since you only have binary operations, you can model any of the calculations as a binary tree where the leaves are numbers and all other nodes are representing operations, e.g. for your first two examples:

  +                  -
 / \                / \
9   +              *   +
   / \            /|  / \
  1   +          2 9 -   1
     / \            / \
    4   2          5   4

So your algorithm would need the following parts:

  • a tree generator for all possible binary trees up to a certain node count: starting with a number node, recursively replace each number node (leaf) with an operator node and two children (number nodes), thus generating a sequence of trees like this

.

N   O       O       O       ...
   / \     / \     / \
  N   N   O   N   N   O
         / \         / \
        N   N       N   N
  • a "tree filler" that generates for a given binary tree (like above) all possible insertions of operations and numbers, like:

.

  O    :    +     +    ...  -  ...
 / \       / \   / \       / \
N   N     1   5 1   2     1   5
  • a tree evaluator that calculates the result

Happy programming! :-)

coproc
  • 6,027
  • 2
  • 20
  • 31