pythonalgorithmdynamic-programmingcoin-change# Finding shortest combinations in array/sequence that equals sum

I'm totally stuck and have no idea how to go about solving this. Let's say I've an array

```
arr = [1, 4, 5, 10]
```

and a number

```
n = 8
```

I need shortest sequence from within arr which equals n. So for example following sequences within arr equals n

```
c1 = 5,1,1,1
c2 = 4,4
c3= 1,1,1,1,1,1,1,1
```

So in above case, our answer is c2 because it's shortest sequences in arr that equals sum.

I'm not sure what's the simplest way of finding a solution to above? Any ideas, or help will be really appreciated.

Thanks!

Edited:

- Fixed the array
- Array will possibly have postive values only.
- I'm not sure how subset problem fixes this, probably due to my own ignorance. Does sub-set algorithm always give the shortest sequence that equals sum? For example, will subset problem identify c2 as the answer in above scenario?

Solution

As has been pointed before this is the minimum change coin problem, typically solved with dynamic programming. Here's a Python implementation solved in time complexity O(nC) and space complexity O(C), where `n`

is the number of coins and `C`

the required amount of money:

```
def min_change(V, C):
table, solution = min_change_table(V, C)
num_coins, coins = table[-1], []
if num_coins == float('inf'):
return []
while C > 0:
coins.append(V[solution[C]])
C -= V[solution[C]]
return coins
def min_change_table(V, C):
m, n = C+1, len(V)
table, solution = [0] * m, [0] * m
for i in xrange(1, m):
minNum, minIdx = float('inf'), -1
for j in xrange(n):
if V[j] <= i and 1 + table[i - V[j]] < minNum:
minNum = 1 + table[i - V[j]]
minIdx = j
table[i] = minNum
solution[i] = minIdx
return (table, solution)
```

In the above functions `V`

is the list of possible coins and `C`

the required amount of money. Now when you call the `min_change`

function the output is as expected:

```
min_change([1,4,5,10], 8)
> [4, 4]
```

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