Write a recursive method named numberPuzzle that uses backtracking to try to find ways of combining a sequence of integers into an arithmetic expression that adds up to a given desired sum.
Your method will be passed two parameters: a list of integers, and an integer representing a desired sum.
You must look for combinations of adding or subtracting each integer in the list to produce the desired sum, and print all such combinations found in a specific format shown below.
For example, suppose a list of integers named numbers stores [2, 3, 6, 9, 5, 7, 1].
If we wanted to combine these numbers to produce a sum of 5 by adding or subtracting each, one example would be: 2 + 3 + 6 - 9 - 5 + 7 + 1.
Your method should print all such combinations of + and - that add up to the given sum in the end.
Therefore the call of numberPuzzle(nums, 5); would produce the following lines of output to the console:
5 = 0 + 2 + 3 + 6 - 9 - 5 + 7 + 1
5 = 0 + 2 + 3 - 6 + 9 + 5 - 7 - 1
5 = 0 + 2 - 3 - 6 + 9 - 5 + 7 + 1
5 = 0 - 2 + 3 + 6 + 9 - 5 - 7 + 1
5 = 0 - 2 + 3 - 6 + 9 - 5 + 7 - 1
5 = 0 - 2 - 3 + 6 - 9 + 5 + 7 + 1
Each line begins with the desired sum, an equals sign, and a 0 to indicate that our summing begins from 0.
You can print the lines of output in any order; you don't have to match our order.
But each line must exactly match our output format, and each line must use every element of the list in their original order as part of the sum.
The vector could contain negative numbers or zeros; treat these the same as any other number.
If there is no way to combine the numbers in the list to get to the given sum, you should not produce any output.
You may assume that the list passed contains at least one integer in it; it will not be empty.
After your method is done running, the list should still contain the same integers in the same order.
Constraints:
Do not declare any global variables.
You can use any data structures you like, and your code can contain loops, but the overall algorithm must be recursive and must use backtracking.
You are allowed to define other "helper" methods if you like; they are subject to these same constraints.
