Pular para o conteúdo

Troco exato com moedas ilimitadas

Fácil#unbounded-knapsack#bottom-up-dp~15 min

A missão

Problema

Uma máquina de venda tem um estoque ilimitado de moedas de cada valor listado em coins. Retorne True se ela consegue devolver exatamente amount; caso contrário, False.

Exemplos

Input:  coins = [4, 7], amount = 15
Output: True
Por quê: 4 + 4 + 7 = 15
Input:  coins = [4, 6], amount = 9
Output: False
Por quê: toda combinação de 4 e 6 dá um número par
Input:  coins = [5], amount = 0
Output: True
Por quê: edge case: pagar zero não precisa de nenhuma moeda

Dicas

0 / 3

Tempo-alvo
O(len(coins) · amount)
Espaço-alvo
O(amount)

Restrições

  • unlimited supply of every coin

Travou na ideia, e não no código? Coin Change explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado