How many ways are there of making change for n, given an array of distinct coins? For example:
Input: n = 4, coins = [1, 2]
Output: 3. 1+1+1+1, 1+2+1, 2+2, would be the ways of making change.
Note that a coin can be used any number of times, and we are counting unique combinations.
Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.
def change_ways(n, coins):
# TODO: Implement me
return n
The following unit test is expected to fail until you solve the challenge.
# %load test_coin_change_ways.py
import unittest
class Challenge(unittest.TestCase):
def test_coin_change_ways(self,solution):
self.assertEqual(solution(0, [1, 2]), 0)
self.assertEqual(solution(100, [1, 2, 3]), 884)
self.assertEqual(solution(1000, range(1, 101)),
15658181104580771094597751280645)
print('Success: test_coin_change_ways')
def main():
test = Challenge()
test.test_coin_change_ways(change_ways)
if __name__ == '__main__':
main()
Review the Solution Notebook for a discussion on algorithms and code solutions.