# CodeStepByStep

## max_sum

Language/Type: Python recursion recursive backtracking

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 non-negative. 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.

Function: Write a Python function as described, not a complete program.