Java BFS solution


  • 0
    D
    public class Solution {
        public int coinChange(int[] coins, int amount) {
            if (amount < 0) return -1;
            if (amount == 0) return 0;
            int n = coins.length;
            if (n == 0) return -1;
            Set<Integer> set = new HashSet<>();
            set.add(0);
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                min = Math.min(min, coins[i]);
            }
            if (amount < min) 
            	return -1;
            int level = 0;
            boolean[] visited = new boolean[amount + 1];
            Arrays.fill(visited, false);
            while (set.size() > 0) {
            	level += 1;
            	Set<Integer> newSet = new HashSet<>();
            	for (int p: set) {
            		for (int i = 0; i < n; i++) {
            			int temp = p + coins[i];
            			if (temp == amount)
            				return level;
            			else if (temp > amount)
            				continue;
            			else if (visited[temp] == false) {
            				visited[temp] = true;
            				newSet.add(temp);
            			}
            		}
            	}
            	set = newSet;
            }
            return -1;
        }
    }

Log in to reply
 

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