
November 8th, 2015, 12:28 PM
#1
How to keep list local to the function call (Recursion) in Python
I'm trying to implement Coin Changing Problem which states that
Coin Changing problem is described as given a value N, if we want to make change for N cents, and we have infinite supply of each of S = {S1, S2, . . . , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. Identify all possible ways of changing N cent by Greedy Method. For example, for N = 4 and S = {1, 2, 3}, there are four solutions: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 2, 6}, {2, 3, 5}and{5, 5}. So the output should be 5.
In my below python implementation I'm using a list name check. Problem is that the program is using same check list throughout its run time and hence I'm getting wromg result. It should use the check list which local to its function call. Can anybody find a way out of this
Code:
# N
N = 10
# Set of Changes
s = [2, 3, 5, 6]
lst = []
check = [0, 0, 0, 0]
def Coin_Change_Count(C, check):
for k in range(len(s)):
i = len(s)  k  1
t = C  s[i]
if (t >= 0):
if (s[i] == 2):
check[0] += 1
elif (s[i] == 3):
check[1] += 1
elif (s[i] == 5):
check[2] += 1
elif (s[i] == 6):
check[3] += 1
if (t >= s[0]):
Coin_Change_Count(t, check)
if (t == 0):
if (not (check in lst)):
lst.append(check)
Coin_Change_Count(N, check)
print(len(lst))
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
