Code Challenge #16: July 26, 2017
Every week, we feature the type of brainteasing question that might be asked in a fullstack developer's job interview at places such as Google and Facebook.
This week's challenge was reported to have been asked in interviews at Google:
The Challenge
You're building an ATM and want to know how many ways you can "break" a given amount of money into cash or change.
To do so, write a function,changeOptions
, that when fed an amount of moneyn
and a list of valuesS = { S1, S2, .. , Sm}
(representing the possible coin or note denominations), will return the number of all the possible ways in which one can break downn
into change.

Function Name:
changeOptions

Input:
n
, an integer≥0
and an integer arrayS
which is the list of all denominations. 
Output: an integer, the number of all of the possible combinations of coins and notes that add up to
n

Example:
changeOptions(5, [1, 2, 5, 10, .., 50000]) => 4
 Where the amount is 5¢ (
n=5
) and the denominations areS = [1, 2, 5, 10, .., 50000]
, the possible combinations of coins and notes that add up to5
are1+1+1+1+1, 1+1+1+2, 1+2+2, 5
, so your function would return4
.  The order of the coins and notes doesn't matter – 2¢+1¢+2¢ is the same amount of money as 2¢+2¢+1¢.
 Where the amount is 5¢ (

n
andS
both represent the number of cents – for example do not use€2.50
as an input, use250
instead.  use as your sample problem
n = 26730
andS = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000]
Hard Difficulty
Write
changeOptions
as efficiently as possible.
Find out more about hard challenges and Big O
Reply
to this thread with a link to your code on repl.it and paste your properly formatted code to participate! Don't just submit your code, remember to explain
your solution, too! If you want to be considered as the winner, your function must
have the correct name
and provide output in the format specified
above, you also need to abide by our other simple rules.
As always solutions using imports to do all the heavy lifting such as itertools
will not be considered for the winner.
The fine print:
Click the links to find out more about:
 the rules & how to participate in challenges
 how challenges are used as job interview questions
 why Codecademy runs challenges (and why they are formatted this way)
 more details about the challenges and why we think they are useful.
 find previous challenges (and see the past winners) in our Challenge Index