Three summers ago def three_summers(items, goal): Given a list of positive integer items guaranteed to contain at least three elements with all of its elements in sorted ascending order, determine...

Three summers ago

def three_summers(items, goal):

Given a list of positive integer items guaranteed to contain at least three elements with all of its elements in sorted ascending order, determine whether there exist precisely three separate items that together add up to the given positive integer goal, no more and no less.

You could, of course, solve this problem with three nested loops to go through all possible ways to choose three elements from items, checking for each triple whether it adds up to the goal. However, this approach would get rather slow as the number of elements in the list increases, and

of course the automated tester used to grade this function will make those lists larger just to make such solutions reveal themselves with their excessive consumption of running time.

Since items are known to be sorted, better technique will find the answer significantly faster. See the new example function two_summers in listproblems.py to quickly find two elements from the given sorted list that together add up to the given goal. You can simply use this function

as a subroutine to speed up your search for three summing elements, once you realize that the list contains three elements that add up to goal if and only if it contains some element x so that the remaining list contains two elements that add up to goal-x.

For the general subset sum problem used as an example of inherently exponential branching recursion in that lecture, the question of whether the given list of integers contains some subset of k elements that together add up to given goal can be determined by trying each element x in turn as

the first element of this subset, and then recursively determining whether the remaining elements after x contain some subset of k - 1 elements that adds up to goal-x

Extracted text: items goal Expected result [10, 11, 16, 18, 19] 40 True [10, 11, 16, 18, 19] 41 False [1, 2, 3] True