Write a recursive function 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 function will be passed two parameters: a reference to a vector of integers, and an integer representing a desired sum.
You must look for combinations of adding or subtracting each integer in the vector to produce the desired sum, and print all such combinations found in a specific format shown below.
For example, suppose a vector 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 function 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 vector 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 vector to get to the given sum, you should not produce any output.
You may assume that the vector passed contains at least one integer in it; it will not be empty.
After your function is done running, the vector 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" functions if you like; they are subject to these same constraints.
