Write a recursive function named rodCutting that solves the classic "rod cutting" problem using backtracking.
The idea is that you are given a rod that can be cut into pieces of various sizes and sold, where each piece fetches a given price in return, and you are trying to find the optimal way to cut the rod to generate the greatest total price.
For example, suppose you have a rod as shown in the following figure that can be cut into pieces of length 1-8:
length 1 2 3 4 5 6 7 8
rod =================================
price 1 5 8 9 10 17 17 20
Your function accepts a reference to a vector of integers representing the various sizes that can be cut, from 1 through the length of the rod inclusive.
For the rod in the preceding figure, the vector would contain the values {1, 5, 8, 9, 10, 17, 17, 20}.
You should return an integer representing the maximum sum that can be obtained by cutting the rod into pieces of any length.
For the rod in the preceding figure, the correct answer is to return 22, which is obtained by cutting the rod into pieces of lengths 2 and 6.
You are allowed to modify the vector passed in as the parameter as you compute the answer, as long as you restore it to its original form by the time the overall call is finished.
You may use loops in solving this problem, but your overall algorithm should utilize recursive backtracking.
