पाइथन में रिकर्सिव के साथ सिक्के बदलें/कोई काम क्यों नहीं?

सरल उपाय

कोड

def coinChange(coins, amount, result=None, solutions = None):
    '''
        result - stores current set of coins being tries
        soltions - solutions found so far
    '''
    if result is None: 
        result = []
        
    if solutions is None:
        solutions = []

    if amount == 0:
        # Add solution
        solutions.append(result[:])  # append a copy since result will change
    elif amount > 0:
        for i in coins:
            if amount - i >= 0:
                # Adding i to list of coins to try
                coinChange(coins, amount - i, result + [i,], solutions)
                
    return solutions
            

परीक्षण

a = coinChange([1,2,3], 3)
print(a)
            
# Capture the solution in a (i.e. don't make it global--generally bad practice)         
a = coinChange([1,2,3], 3)
print(a)

आउटपुट

[[1, 1, 1], [1, 2], [2, 1], [3]]

जेनरेटर का उपयोग करना और भी आसान

def coinChange(coins, amount, result=None):
    '''
        result - stores current set of coins being tries
        soltions - solutions found so far
    '''
    if result is None: 
        result = []
        
    if amount == 0:
        # report solution
        yield result
        
    if amount > 0:
        for i in coins:
            yield from coinChange(coins, amount - i, result + [i,])    
            
a = list(coinChange([1,2,3], 3))
print(a)

कैश का उपयोग करना

GalSuchetzky उत्तर को संशोधित करके कैश के उपयोग को स्पष्ट करना सबसे आसान है।

समस्या

• कॉइनचेंज फंक्शन पर सीधे कैश का उपयोग नहीं कर सकते क्योंकि तर्क हैशेबल नहीं हैं (जैसे सिक्के एक सूची है, इसलिए हैशेबल नहीं)
• हम इसे नेस्टेड फ़ंक्शन (हेल्पर) का उपयोग करके वापस प्राप्त करते हैं, जिनके तर्क हैशबल हैं जो आवश्यकतानुसार सिक्कों में अनुक्रमित होते हैं

कोड

def coinChange(coins, sum_):
    '''
        Inputs:
            coins - list of coins
            sum_  - value coin should sum to (use sum_ since sum is a builtin function)
    '''
    
    def coinChangeHelper(j, total):
        '''
            Uses cache to compute solutions
            
            Need helper function since coins is a list so can't be hashed to placed in cache
            
            Inputs:
                j     - current index into coins
                total - current sum
        '''
        if (j, total) in mem_cache:
            # Use cache value
            return mem_cache[(j, total)]
        
        # Stop condition.
        if total == 0:
            mem_cache[(j, total)] = [[]]
        else:
            # Recursive step
            solutions = []

            for i in range(j, len(coins)):
                if coins[i] <= total:
                    lst = coinChangeHelper(i, total - coins[i])
                    solutions.extend([[coins[i]] + l for l in lst])

            mem_cache[(j, total)] = solutions
        
        return mem_cache[(j, total)]

    # Init cache
    mem_cache = {}
    
    return coinChangeHelper(0, sum_)

print(coinChange([1, 2, 3], 3))