Write a recursive function max_sum
that accepts a list of integers L and an integer limit n as its parameters and uses backtracking to find the maximum sum that can be generated by adding elements of L that does not exceed n.
For example, if you are given the list of integers [7, 30, 8, 22, 6, 1, 14]
and the limit of 19, the maximum sum that can be generated that does not exceed is 16, achieved by adding 7, 8, and 1.
If the list L is empty, or if the limit is not a positive integer, or all of L's values exceed the limit, return 0
.
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 a list, in which case each occurrence might be added to the sum.
For example, if the list is [6, 2, 6, 1]
you may use up to two sixes in the sum.
Here are several example calls to your function and their expected return values:
List L 
Limit n 
max_sum(L, n) returns 
[7, 30, 8, 22, 6, 1, 14]

19

16

[5, 30, 15, 13, 8]

42

41

[30, 15, 20]

40

35

[6, 2, 6, 9, 1]

30

24

[11, 5, 3, 7, 2]

14

14

[10, 20, 30]

7

0

[10, 20, 30]

20

20

[]

10

0

You may assume that all values in the list are nonnegative.
Your function may alter the contents of the list L as it executes, but L should be restored to its original state before your function returns.
Do not use any loops in solving this problem.