[HackerRank] The Coin Change Problem

https://www.hackerrank.com/challenges/coin-change/problem

def get_ways(n, c):

return [[]] if n == 0 else [[b, *j] for i, b in enumerate(c) if b <= n for j in get_ways(n - b, c[i:])]

n = int(input("Target Change: ").strip())

c = list(map(int, input("Coin List: ").strip().split()))

c.sort()

ways = get_ways(n, c)

print("Number of Ways:", len(ways))

print("List of Ways:", ways)

# Python 3

def get_ways(change, coins):

my_ways = []

for i, coin in enumerate(coins):

if change == coin:

my_ways.append([coin])

elif change - coin >= coin:

for way in get_ways(change - coin, coins[i:]):

my_ways.append([coin, *way])

return my_ways

n = int(input("Target Change: ").strip())

c = list(map(int, input("Coin List: ").strip().split()))

c.sort()

ways = get_ways(n, c)

print("Number of Ways:", len(ways))

print("List of Ways:", ways)

# Python 3

def get_ways(change, coins):

my_ways = [[] for _ in range(change + 1)]

for coin in coins:

for i in range(coin, change + 1):

if i - coin == 0:

my_ways[i].append([coin])

else:

for new_way in [[*way, coin] for way in my_ways[i - coin]]:

my_ways[i].append(new_way)

return my_ways[change]

n = int(input("Target Change: ").strip())

c = list(map(int, input("Coin List: ").strip().split()))

c.sort()

ways = get_ways(n, c)

print("Number of Ways:", len(ways))

print("List of Ways:", ways)