Write a recursive method named largestSum that accepts a list of integers and an integer limit N as parameters and uses backtracking to find the largest sum that can be generated by adding elements of the list that does not exceed N.
For example, if you are given the list [7, 30, 8, 22, 6, 1, 14] and the limit of 19, the largest sum that can be generated that does not exceed is 16, achieved by adding 7, 8, and 1.
If the list is empty, or if the limit is not a positive integer, or all of the list's values exceed the limit, return 0.
Assume that all values in the list are non-negative.
Each index's element in the list can be added to the sum only once, but the same number value might occur more than once in the list, in which case each occurrence might be added to the sum.
For example, if the list is [6, 2, 1] you may use up to one 6 in the sum, but if the list is [6, 2, 6, 1] you may use up to two sixes.
For the most part you do not need to worry about efficiency, but your code should not perform exactly the same unnecessary deep exploration multiple times.
You should also avoid making copies of data structures extremely high numbers of times by always passing them by reference.
The list passed to your method must be back to its original state at the end of the call.
Either do not modify it, or if you modify it, fully undo your modifications before the method returns.
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.
