Find ways to calculate a target from elements of specified array

Write a program to count number of ways to calculate a target number from elements of specified array by using only addition and subtraction operator. The use of any other operator is forbidden.

 

For example, consider the array { 5, 3, -6, 2 }. The number of ways to reach a target of 6 using only + and – operators is 4 as


(-)-6 = 6
(+) 5 (+) 3 (-) 2 = 6
(+) 5 (-) 3 (-) -6 (-) 2 = 6
(-) 5 (+) 3 (-) -6 (+) 2 = 6

Similarly, there are 4 ways to calculate the target of 4:


(-)-6 (-) 2 = 4
(-) 5 (+) 3 (-)-6 = 4
(+) 5 (-) 3 (+) 2 = 4
(+) 5 (+) 3 (+)-6 (+) 2 = 4

 
The idea is to use recursion to solve this problem. We recursively consider each element of the array, and for every element we add or subtract its value from target and recurse for remaining elements with the remaining target. We also recurse with remaining elements with the same target, by ignore the element completely. Finally, we return the number of times the desired target is reached at any point in the recursion.

 
C implementation –

 

Download   Run Code

Output:

4 ways

 
Above solution is very similar to the famous 0-1 Knapsack Problem and runs in O(3^n) time. Dynamic Programming solution is recommended for large input, implementation of which is left as exercise to the readers.
 

How can we extend the solution to print all pairs?

 
We can easily extend the solution to print all pairs of elements. The idea is to maintain a list that stores the processed elements at any point, along with the information about the operator used.

 
C++ implementation –

 

Download   Run Code

Output:

(-)-6
(+)2 (-)-6 (+)3 (-)5
(-)2 (+)3 (+)5
(-)2 (-)-6 (-)3 (+)5

 

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz