# 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.

Output:

4 ways

## Java

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.

## Java

Output:

(-)-6
(+)2 (-)-6 (+)3 (-)5
(-)2 (+)3 (+)5
(-)2 (-)-6 (-)3 (+)5     (2 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest

My bad attempt to rewrite to dynamic programming. The biggest problem is that the current profit can be <0 (like -5 + 3 = -2) and there wasn't a good way to represent -2 as an array index.
This means that if the max value is 500, you create an array of 1000 items and use index 0 to represent -500, index 500 to represent 0 and index 1000 to represent 500. And the logical index -2 will be the actual index 498.
```.. var dp = []; var maxProfit = 0; for (var i = 0; i < items.length; i++) { ..maxProfit += Math.abs(items[i]); ..dp[i] = []; } for (var i = 0; i < items.length; i++) {.. ..for (var s = -maxProfit; s <= maxProfit; s++) { ....var j = maxProfit + s; ....if (s == 0) { ......// 0 profit is a special case ......dp[i][j] = 1; ......continue; ....} ....if (!dp[i][j]) { ......dp[i][j] = 0; ....} ....if (i == 0) { ......// another special case for the first element ......if (s - items[i] == 0 || s + items[i] == 0) { ........dp[i][j] = 1; ......} ......continue; ....} .... ....if (j - items[i] >= 0) { ......dp[i][j] += (dp[i - 1][j - items[i]] || 0); ....} ....if (j + items[i] >= 0) { ......dp[i][j] += (dp[i - 1][j + items[i]] || 0); ....} .... ....dp[i][j] += dp[i - 1][j]; ..} }```

``` ```

```var result = dp[items.length - 1][maxProfit + target]; ..``` Guest

The following statement contains typo:

int include = countWays(arr, n – 1, target – arr[n]) +
countWays(arr, n – 1, target + arr[n]);

It should be arr[n-1] instead of arr[n]