This solution basically should be the same as DP.

The idea is just to repeatedly sum up each coin elements with others.

Example:

```
amount: 15
coins: [1, 2, 5]
1st level nodes [1, 2, 5]
2nd level nodes [1+1, 1+2, 1+5, 2+1, 2+2, 2+5, 5+1, 5+2, 5+5]
3rd level nodes [1+1+1, 1+1+2, 1+1+5, 1+2+1, ... 5+5+5] <= 15 matches! answer = 3.
```

It's kind of BST and `level`

exactly means the number of coins we use.

Obviously we will see the same sum value during the traversal, so we can use *map* to memorize the value already added to the queue. This eventually prevents "many numbers of small coins" from appearing as a solution, because "small numbers of large coins" always take the amount first.

For example, in the example above, we will see `2`

as a result of 2 times of `1`

coins but that already achieved by 1 times of `2`

, so we can discard `1+1`

, no need to add to the queue.

Also we don't need to add the sum if it becomes greater than `amount`

, since there is no chance to match.

The calculation of complexity is bit difficult.

But I think, since we memorize pre-added value, in worst case scenario the queue will have `0`

to `amount`

as an element. Then we have `len(coins)`

inside the outer loop of queue, we can say time complexity is `O(amount*len(coins))`

.

Also, both the queue and map will hold `0`

to `amount`

at most, so space complexity can be said as `O(amount)`

.

This should be the same as DP solution.

```
func coinChange(coins []int, amount int) int {
// corner case, amount = 0
if amount == 0 {
return 0
}
// visited memorized calculated sum-amount
queue, visited := []int{0}, make(map[int]bool)
level, sum := 0, 0
for len(queue) > 0 {
qlen := len(queue)
for i := 0; i < qlen; i++ {
cur := queue[0]
for j := 0; j < len(coins); j++ {
sum = cur + coins[j]
if cur + coins[j] == amount {
return level + 1
}
if cur + coins[j] > amount {
continue
}
if _, ok := visited[sum]; ok {
continue
}
queue, visited[sum] = append(queue, sum), true
}
queue = queue[1:]
}
level++
}
return -1
}
```