Question 2: Iterating over all subsets with a given sum Here is an iterator that yields all the subsets of a given set: empty set. ### def subsets(s) : **"Given set s, yield all the subsets of S, including s itself and the if len(s) = 0: yield set else: set(s) X = ss.pop() for t in subsets (ss): yield t yield t l {x} Your goal is to write an iterator that iterates over all the subsets with a given sum. In detail, you should write a function constant_sum_subsets (values, total), that takes as input: a set values of non-negative numbers; a non-negative number total, and returns an iterator that yields all subsets of values that sum to total. For instance, if values is {1,2,3} and total is 3, then constant_sum_subsets (values, total) yields {1, 2}, and {3}, because those are the subsets of {1,2,3} whose elements sum to 3. Note: A quick and dirty way of doing this is to use either itertools or the subset function above to get an iterator over all subsets of values, and then filter only those which sum to total. Don't do this. Your code will be incredibly inefficient if only few subsets sum to total, and will in particualr fail a test case. Rather, try to encode the requirement of what subsets need to sum to into the recursion. [17] def constant_sum_subsets (values, total): ### YOUR CODE HERE [ ] # This is a place where you can write additional tests to help you test [17] def constant_sum_subsets (values, total): ### YOUR CODE HERE [] # This is a place where you can write additional tests to help you test # your code, or debugging code, if you need. You can also leave it blank. ### YOUR CODE HERE [] for seq in constant_sum_subsets({1, 2, 3}, 3): print (sed) [] for seq in constant_sum_subsets({1, 2, 3, 4, 5, 6, 7, 8}, 8): print (se) ### Simple tests. 10 points. = subs1 constant_sum_subsets({1, 2, 3), 3) subs2 {(1, 2), (3,)} # To represent {{1, 2}, {3}} check_equal (subsets_set(subsi), subsets_set(subs2)) = subs1 = constant_sum_subsets({1, 2, 3, 4], 4) subs2 {(1, 3), (4,)} # To represent {{1, 3}, {4}} check_equal (subsets_set(subsi), subsets_set(subs2)) = subs1 constant_sum_subsets({1, 2, 3, 4, 5}, 6) subs2 {(1, 2, 3), (1, 5), (2, 4)} # To represent {{1, 2, 3}, check_equal (subsets_set(subsl), subsets_set(subs2)) {1, 5}, {2, 4}} [ ### Advanced test. 10 points. are fact that values are all non-negatives. # This test fails if you not Smart about using the values set (range (10000, 10100)) nu 0 for in constant_sun_subsets (values, 2000): 1 check_equal (num, 0) nu + [] ### Advanced test. 10 points. Smart about using the fact that values are all non-negatives. = # This test fails if you not values set(range (10000, 10100)) nun 0 for in constant_sum_subsets (values, 1 check_equal (num, 0) 2000): Ii1III + values = set (range (10000, 10100)) nu 0 for in constant_sum_subsets (values, num + 1 check_equal (num, 10) 20020): [] ### Final tests, # This Compares hidden. 10 points. your solution with a known good solution. pass
