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

Download   Run Code

Output:

4 ways

Java

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++

Download   Run Code

Java

Download   Run Code

Output:

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

 

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

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 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Wolf
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];
..