In Chapter $6$ we wrote the subset function that determines whether or not there exists a subset of the numberList that adds up to the target. The code that we developed is here:

def subset$($target$,$ numberList$)$:

$\text{'}\text{'}\text{'}$ Returns True if there exists a subset of numberList that adds

$$ up to target and returns False otherwise.$\text{'}\text{'}\text{'}$

$$ if target $==0$: return True

$$ elif numberList $==[]$: return False

$$ if numberList$[0]>$ target: return subset$($target$,$ numberList$[1$:$])$

$$ else:

$$ useIt $=$ subset$($target $-$ numberList$[0],$ numberList$[1$:$])$

$$ loseIt $=$ subset$($target$,$ numberList$[1$:$])$

$$ return useIt or loseIt

Unfortunately, this function can become very slow as the inputs become "large". Cut$-$and$-$paste into your own file and try running it on the following

$>>>$ subset$(1234567,$ range$(2,100,2))$

$($What is that range$(2,100,2)$ doing?$)$

The subset function is slow because it does a large number of redundant calculations. Your task now is to write a much faster memoized version called memoizedSubset. As we saw with the change function that we memoized in the text, we will want to give this new function a tuple input instead of a list. Our new function will look like this: memoizedSubset$($ target, numberTuple, memo $).$

After you've written it$,$ try the same inputs with this new, faster function:

$>>>$ numberTuple $=$ tuple$($range$(2,100,2))$

$>>>$ memoizedSubset$(1234567,$ numberTuple, $\{\})$