coin changes number of ways.

orsenthil · orsenthil · commit 5f32c1bdfb4e · 2016-03-13T13:59:39.000-07:00
diff --git a/python/dynamic/coin_change_num_ways.py b/python/dynamic/coin_change_num_ways.py
@@ -0,0 +1,78 @@
+"""
+Problem Statement
+=================
+
+Given a total and coins of certain denominations find number of ways total can be formed from coins assuming infinity
+supply of coins.
+
+Analysis
+--------
+* Runtime : O(num_of_coins * total)
+
+Video
+-----
+* https://youtu.be/_fgjrs570YE
+
+Reference
+---------
+* http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
+"""
+
+
+def coin_changing_num_ways(coins, total):
+    cols = total + 1   # 1 for value 0 in total
+    rows = len(coins)
+    T = [[1 if col == 0 else 0 for col in range(cols)] for _ in range(rows)]
+
+    for i in range(rows):
+        for j in range(cols):
+            if (i - 1) < 0:
+                T[i][j] = 1
+                continue
+            if j < coins[i]:
+                T[i][j] = T[i - 1][j]
+            else:
+                T[i][j] = T[i - 1][j] + T[i][j - coins[i]]
+
+    return T[rows - 1][cols - 1]
+
+
+def coin_changing_num_ways2(coins, total):
+    cols = total + 1
+    num_coins = len(coins)
+
+    # Using 1-D Array instead of 2-D Array. Approach is same as coin_changing_num_ways.
+    T = [1 if col == 0 else 0 for col in range(cols)]
+
+    for i in range(num_coins):
+        for col in range(1, cols):
+            if col >= coins[i]:
+                T[col] += T[col - coins[i]]
+
+    return T[cols - 1]
+
+
+def print_coin_changes_recursive(coins, total, results_stack, pos):
+    if total == 0:
+        for coin in results_stack:
+            print "%d " % coin,
+        print
+
+    for idx in range(pos, len(coins)):
+        if total >= coins[idx]:
+            results_stack.append(coins[idx])
+            print_coin_changes_recursive(coins, total - coins[idx], results_stack, idx)
+            results_stack.pop()        # Remove last inserted coin from stack to use new coin with different index.
+
+
+def print_coin_changes(coins, total):
+    print_coin_changes_recursive(coins, total, list(), 0)
+
+
+if __name__ == '__main__':
+    coins = [1, 2, 3]
+    total = 5
+    expected = 5
+    assert expected == coin_changing_num_ways(coins, total)
+    assert expected == coin_changing_num_ways2(coins, total)
+    print_coin_changes(coins, total)
