USE PYTHON3; DO NOT IMPORT ANY PACKAGES

Please do both parts a and b and follow the directions carefully. Thank you!

a)

Write a recursive function that takes two sequences of numeric values (main and sub), and calculate two kinds of sum of the main sequence:

1. Sum of intersection: the sum of all numbers in the main sequence that also appear in the sub sequence.

2. Sum of differences: the sum of all numbers in the main sequence that do not appear in the sub sequence.

This function should return a tuple of (sum_of_intersection, sum_of_difference), if the main sequence is empty, return (0, 0).

You CANNOT use sum(), range(), or any loops/list comprehensions.

def find_two_sums_rec(main, sub):

"""

>>> main_seq = [0, 1, 1, 2, 3, 3, 4, 5, 5]

>>> find_two_sums_rec(main_seq, [])

(0, 24)

>>> find_two_sums_rec(main_seq, [1, 2])

(4, 20)

>>> find_two_sums_rec(main_seq, [3, 4, 5])

(20, 4)

"""

# YOUR CODE GOES HERE #

b)

Write a recursive function that takes a list of positive integers (nums, not empty) and a positive integer target, and find whether its possible to pick a combination of integers from nums, such that their sum equals the target. Return True if we can pick such a combination of numbers from nums; otherwise, return False.

Hints:

1. For each recursive call, you should only deal with one number in the list. Think about how to approach these sub-problems with recursion: if we include this number in the combination, can we reach the target sum? How about excluding this number from the combination?

2. Although we assume that the initial arguments are positive integers and the initial nums list is not empty, you might observe that, at some point, a recursive call will receive arguments that violate these assumptions (for example, the nums list becomes empty). You might find it helpful to treat these situations as base cases.

Examples:

nums	target	output
[3, 34, 4, 12, 5, 2]	9	True
[1, 1, 1]	9	False
[1, 10, 9, 8]	17	True

def group_summation(nums, target):

"""

>>> group_summation([3, 34, 4, 12, 5, 2], 9)

True

>>> group_summation([1, 1, 1], 9)

False

>>> group_summation([1, 10, 9, 8], 17)

True

"""

# YOUR CODE GOES HERE #