Three summers ago def three_summers(items, goal): Given a sorted list of positive integer items, determine whether there exist precisely three separate items that together exactly add up to the given positive integer goal. Sure, you could 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, iterating through all triples of elements would get pretty slow as the length of the list increases, seeing that the number of such triples to pick through grows proportionally to the cube of the length of the list! Of course the automated tester will make those lists large enough to make such solutions reveal themselves by their glacial running time. Since items are known to be sorted, a better technique will 0ind the answer significantly faster. See the function two_summers in the example program listproblems.py to quickly find two elements in the given sorted list that together add up to the given goal. You can 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 some two elements that add up to goal-x. items goal Expected result [10, 11, 16, 18, 19] 40 True [10, 11, 16, 18, 19] 41 False [1, 2, 3] 6 True For the general subset sum problem that was 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. Code that is already available on the site times out in my tester. Is there a faster approach? def three_summers(items, goal): for i in range(len(items)): for j in range(i+1, len(items)): for k in range(j+1, len(items)): if items[i] + items[j] + items[k] == goal: return True return False
Three summers ago
def three_summers(items, goal):
Given a sorted list of positive integer items, determine whether there exist precisely three separate items that together exactly add up to the given positive integer goal.
Sure, you could 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, iterating through all triples of elements would get pretty slow as the length of the list increases, seeing that the number of such triples to pick through grows proportionally to the cube of the length of the list! Of course the automated tester will make those lists large enough to make such solutions reveal themselves by their glacial running time.
Since items are known to be sorted, a better technique will 0ind the answer significantly faster. See the function two_summers in the example program listproblems.py to quickly find two elements in the given sorted list that together add up to the given goal. You can 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 some two elements that add up to goal-x.
|
items |
goal |
Expected result |
|
[10, 11, 16, 18, 19]
|
40 |
True |
|
[10, 11, 16, 18, 19]
|
41 |
False |
|
[1, 2, 3] |
6 |
True |
For the general subset sum problem that was 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.
Code that is already available on the site times out in my tester. Is there a faster approach?
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 2 images
