You get a list nums of whole numbers. Return the sum of all its numbers.
Solve it with recursion, a function that calls itself. A loop would work too, but this lesson is about the recursive call.
The sum of an empty list is 0.
Example 1:
Input: nums = [3,8,-5,10,2] Output: 18 Explanation: 3 + 8 - 5 + 10 + 2 = 18.
Example 2:
Input: nums = [-6] Output: -6 Explanation: With one number, the sum is that number.
Example 3:
Input: nums = [] Output: 0 Explanation: There are no numbers to add.
Constraints:
- 0 to 1,000 numbers.
- Each number is from -10,000 to 10,000.
Your solution should run in O(n) time, where n is the length of nums.
The sum of the whole list is its first number plus the sum of the numbers after it. That second sum is the same problem, with one number fewer.
Give the recursive function an index
i, where its part of the list starts. Each call moves i one step to the right. When i is past the last number, nothing is left, so return 0.
There are n + 1 calls, and each one does a fixed amount of work: O(n) time.
Each call waits for the next one, so up to n + 1 calls sit on the call stack at once: O(n) extra space. That is also why
nums holds at most 1,000 numbers here.Passing a copy of the rest of the list to each call, instead of an index, would cost O(n2) time.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
