Golang solution using BFS and caching visited amount, with explanation


  • 0

    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
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.