-
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
|