pythonrecursiondata-structuresbacktrackingcoin-change# Understanding a LeetCode recursion problem in Python (322 Coin Change)

## Leetcode Question: https://leetcode.com/problems/coin-change/

322 Coin Change:

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

```
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Example 3:
Input: coins = [1], amount = 0
Output: 0
Example 4:
Input: coins = [1,4,5], amount = 8
Output: 2
Explanation: 8 = 4 + 4
```

So, I have been struggling with recursion and been practicing all different sorts of problems from DFS, BFS, Perms, Combos, Subsets etc, and making a little progress but not quite where I want to be for interviews.

I know this problem can be solved with DP but before moving on that concept I want to solve it using DFS to understand the problem first. I couldn't find a DFS example on the solutions.

So here is my first attempt and I keep failing some cases e.g. `[186,419,83,408], 6249`

.

Here was my thought process for the code below.

- The reverse is not needed I just have it there to make it faster in the debugger
- I am going to set up a backtracking template and loop through all the indexes trying every option
- If I match the answer I return (this might be why it's wrong since I am never popping off the total amount and there might be another option with fewer coins)
- I keep calling backtracking trying to increment by the same coin until it doesn't work
- if it fails I call another backtrack function incrementing the index to attempt to reach the final result

From someone more experienced: how would you have solved this problem / recognized the pattern? My original attempt was the greedy algorithm but I quickly found out that didn't work.

Maybe I should research more Top-Down bottom-up approaches but any advice on how to continue to get better or practice would be greatly appreciated. I spend a bunch of time in the debugger trying to understand these problems. I feel like giving up all the time but know that is not an option and is part of the learning curve.

```
def coinChange(self, coins: List[int], amount: int) -> int:
coins = coins[::-1]
minCoin = inf
def backtrack(i,total,count):
nonlocal minCoin
if total == amount:
minCoin = min(minCoin,count)
return
if total + coins[i] <= amount:
count += 1
backtrack(i,total + coins[i],count)
if i + 1 < len(coins):
backtrack(i+1,total,count)
for i in range(len(coins)):
backtrack(i,0,0)
return minCoin if minCoin != inf else -1
```

Solution

I think your code is failing because of passing index parameter "i". The problem statement says:

You may assume that you have an infinite number of each kind of coin.

that means if `total + coins[i] <= amount`

you have to do a for-loop for all coins. in your code you have to start from the 0'th index but you are starting backtracking from the same index.

In recursive problems, it would be easier to be able to visualize a decision tree.

for each num in nums, you recursively make a new call for new target `target-num`

. if you reach the leaf node, return empty array []. As you pull back to the root, add the num to the array in each level. While you make recursive call you should also be tracking the shortest path so far in memory and if you return a valid result array, compare the result with the shortest array so far and update the shortest array

```
from typing import List
class Solution:
def coinChange(self, nums: List[int], target: int) -> int:
def dfs(target, memo={}):
# without memoization it wont pass
if target in memo:
return memo[target]
# base case changes depending on your logic
if target == 0:
return []
if target < 0:
return None
shortest_combination = None
for num in nums:
remainder = target - num
# this is where the decision tree is built
result = dfs(remainder)
# make sure not if result because result might be [] which yields to False
if result != None:
# combination = result+[num]
combination = [*result, num]
# when we get the first result, we assign shortest_combination to that result.
# so shortest_combination == None this will be true only once
if shortest_combination == None or len(combination) < len(shortest_combination):
shortest_combination = combination
memo[target] = shortest_combination
return shortest_combination
return -1 if dfs(target) == None else len(dfs(target))
```

- Python Jinja2 LaTeX Table
- Getting attributes of a class
- How can I print many significant figures in Python?
- How to allow list append() method to return the new list
- Calculate Last Friday of Month in Pandas
- Python type hint for Iterable[str] that isn't str
- How to iterate over a list in chunks
- How to exit the entire application from a Python thread?
- Running shell command and capturing the output
- How do I pass a variable by reference?
- Convert range(r) to list of strings of length 2 in python
- How can I get the start and end dates for each week?
- how to use send_message() in python-telegram-bot
- Python conditional replacement based on element type
- How can I count the number of items in an arbitrary iterable (such as a generator)?
- Find longest consecutive range of numbers in list
- Insert text in braces with asyncpg
- How does one put a link / url to the web-site's home page in Django?
- How to determine if a path is a subdirectory of another?
- Custom Keybindings for Ipython terminal
- FastAPI asynchronous background tasks blocks other requests?
- How to make sure that information from one file is duplicated into several text documents, without specific lines
- Installing a Python environment with Anaconda
- sklearn pipeline model predicting same results for all input
- Brew command not found after installing Anaconda Python
- How to get an XPath from selenium webelement or from lxml?
- Pipe PuTTY console to Python script
- How to align the axes of a figure in matplotlib?
- Persist ParentDocumentRetriever of langchain
- How to reset index in a pandas dataframe?