# Forming arithmetic expression meeting target value

Given n integers and a target value form an arithmetic expression evaluating to the target value.

## Summary

You are given the integers 3, 100, 8, 8, 10, 6 and need to approach the target value 683. The allowed operations are addition, multiplication, subtraction (only if the result is positive) and division (only if the result is integer). And every given integer can appear at most once in the solution. A solution in this example would be

```
6 * 100 + 8 * 10 + 3 = 683.
```

## Complexity

One can use dynamic programming to solve the problem, even though the resulting complexity would be huge.

We could upper bound it by the number of arithmetic expressions one can form with the given numbers, regardless of the restrictions on the subtraction and division. Then even restricting to expressions involving all n given numbers there are quite many expressions. An expression can be viewed as a binary tree with n leafs, and hence n-1 inner nodes. The number of those trees is the Catalan number $C_{n-1}$, which is $(2n-2)!/(n!(n-1)!)$. This number needs to be multiplied by $4^{n-1}$ corresponding to the number of possibilities to assign one of the four operators to each of the inner nodes.

Due to the constraints on subtractions and divisions, the actual number of valid expressions might be smaller than this rough estimation, but nevertheless it is huge. Hence the algorithm is practical only for small n, say less than 10.

### Dynamic Program

Let $x_0,x_1,\ldots,x_{n-1}$ be the given integers.
We denote by $S\subseteq\{0,1,\ldots,n-1\}$ a selection of these integers.
In a table `expr`

we store for every set S in `expr[S]`

a dictionary. It contains (key, value) pairs of the form `(v,f)`

where `f`

is a valid arithmetic expression formed by the integers $\{x_i:i\in S\}$ and `v`

is the value of `f`

.

Initially `expr[{i}]`

is a dictionary associating to the value $x_i$ the singleton expression $x_i$. Then for every non-singleton set $S$ we populate the dictionary `expr[S]`

as follows.
Any arithmetic expression involving the integers $\{x_i:i\in S\}$ consists of an arithmetic expression tree with some operator `op`

in the root and a left subtree over a set $L$ and a right subtree over a set $R$ where $L$ and $R$ are non-empty sets partitioning $S$. Therefore for fixed set $S$ we loop over all non-empty strict subsets $L\subset S$. For each $L$ we set $R=S\setminus L$ and loop over all values $v_L$ in `expr[L]`

and all values $v_R$ in `expr[R]`

. Now for each operator `op`

among +,*,-,/ for which $v:=v_L \textrm{op} v_R$ is a valid expression we can associate in `expr[S]`

to the key $v$ the expression `expr[L][`

$v_L$`] op expr[R][`

$v_R$`]`

.

These operations need to be done for all sets $S$ in a lexicographical order that ensures that all subsets of $S$ have already been processed.

### Implementation details

Since $n$ is a very small number it is most convenient for us to represents sets as integers. For example the set $S={1,3,4}$ is represented as the integer $2^0 + 2^3 + 2^4$. This has the advantage that bit manipulation operators can be used to encode set operators. For example the bitwise and denoted `&`

corresponds to the intersection and the test `L & S == L`

tests whether the set encoded by $L$ is a subset of the set encoded by $S$.