I'm supposed to determine a Recursive way of finding all the possible combinations of the + and - operators inserted into an array from 1 to N, so that the final result will equal another given number K. An example would be:
For N = 6 and K = 3
1 + 2 + 3 - 4 - 5 + 6 = 3
1 + 2 - 3 + 4 + 5 - 6 = 3
1 - 2 - 3 - 4 + 5 + 6 = 3
I've been given a hint where I'm supposed to compute and F(N - 1) which gives a K1 = K - N and K2 = K + N, and if the result reaches an F(0) = 1 then the resulted operators in order would compute to a correct answer.
I've tried this approach but so far it worked only in situations where all operators are identical (ex. 1 + 2 + 3 = 6), and can't manage to understand how to use it to solve the more complex situations. The algorithm should be implemented in a recursive method, without using data structures, just plain arrays and recursion.
Any idea how this would work or any other ideas?
Thank you!!
Both $N$ and $K$ are given, so you'll want to think of your function as depending on both. We'll call the function $F(N, K)$. If $1 ... \pm N = K$, then $1 ... N - 1 = K \mp N$. So the solutions for $N$ and $K$ are in one-to-one correspondence with the solutions for $N - 1$ and $K - N$ together with the solutions for $N - 1$ and $K + N$. That means that $F(N, K) = F(N - 1, K + N) + F(N - 1, K - N)$.
You'll want to also figure out the base case(s) (what happens when N = 0?). Also, there's the subtle question about what to do with $1$. It seems to be implied that $1$ has to be positive (no negative sign inserted in front of it), so you may want to make $N = 1$ be the base case instead.
For an example, take $N = 4$ and $K = 6$.
$$ \begin{aligned} F(4, 6) & = F(3, 2) + F(3, 10) \\ & = F(2, -1) + F(2, 5) + F(2, 7) + F(2, 13) \\ & = F(1, -3) + F(1, 1) + F(1, 3) + F(1, 7) + F(1, 5) + F(1, 9) + F(1, 11) + F(1, 15) \\ & = 0 + 1 + 0 + 0 + 0 + 0 + 0 + 0 \\ & = 1 \end{aligned} $$
To actually figure out what combination of plus and minus would solve the problem, follow the tree upwards: $F(1, 1) \to F(2, -1) \to F(3, 2) \to F(4, 6)$. So it's $1 - 2 + 3 + 4 = 6$