Quote:

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

Python provides a find(substring, start, end) string method that returns the lowest index (integer) where the substring is found in the index range start ≤ index < end. The start and end arguments are optional, but for this exercise, we will make them required. If the substring is not found -1 is returned.

Functions to Add

find(input_string, substring, start, end)

Without using the find string method write a function that behaves exactly like the find string method. This means you’ll have to write a loop to do letter by letter comparisons. As your function is not a string method, the string to search must be an argument.

multi_find(input_string, substring, start, end)

Biology researchers frequently want to find all the locations where a substring is found, not simply the first one. Write a function that, instead of returning one integer index, returns a string with zero or more indices separated by commas. In this case, the string will contain digits representing the

integer indices. If the substring is not found, an empty string is returned. You may use the find function from part a. ]]>