# Java - BFS easy to understand

• ``````public class Solution {
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
Set<Integer> set = new HashSet<>();
int count = 1;
if (amount == 0)
return 0;

for (Integer coin : coins)
{
if (amount == coin)
return count;
else if (amount > coin)
}

while (true)
{
Set<Integer> newSet = new HashSet<>();
count++;
for (int newAmount : set)
{
for (int coin : coins)
{
if (newAmount == coin)
return count;
else if (newAmount > coin)
{
if (newAmount - coin >= coins[0])
}
else
break;
}
}

if (newSet.isEmpty())
break;
else
set = newSet;
}

return -1;
}
}
``````

Updated to use array:

``````public class Solution {
public int coinChange(int[] coins, int amount) {
int coinsLength = coins.length;
Arrays.sort(coins);
Queue<Integer> q = new LinkedList<>();
int count = 1;
if (amount == 0)
return 0;
boolean[] cache = new boolean[amount];
//Set<Integer> cache = new HashSet<>();

for (Integer coin : coins)
{
if (amount == coin)
return count;
else if (amount > coin)
{
cache[amount - coin] = true;
}
}

while (true)
{
Queue<Integer> newQ = new LinkedList<>();
count++;
while (!q.isEmpty())
{
int newAmount = q.poll();
for (int i = coinsLength - 1; i >= 0; i--)
{
if (newAmount == coins[i])
return count;
else if (newAmount > coins[i])
{
int value = newAmount - coins[i];
if (value >= coins[0] && !cache[value])
{
cache[value] = true;
}
}
}
}

if (newQ.isEmpty())
break;
else
q = newQ;
}

return -1;
}
}``````

• Try to store results into an int array, it would be much faster than using HashSet.

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