Pular para o conteúdo

Vales-presente para um total exato

Fácil#0-1-knapsack#subset-sum~20 min

A missão

Problema

Você tem vales-presente com os valores em cards, e cada vale pode ser usado no máximo uma vez. Um vale precisa ser usado por inteiro. Retorne True se alguns dos vales somarem exatamente total; caso contrário, False.

Exemplos

Input:  cards = [3, 34, 4, 12, 5, 2], total = 9
Output: True
Por quê: 4 + 5 = 9
Input:  cards = [3, 34, 4, 12, 5, 2], total = 30
Output: False
Por quê: os vales pequenos somam só 26, e o vale de 34 sozinho já é demais
Input:  cards = [7], total = 0
Output: True
Por quê: edge case: não usar nenhum vale paga exatamente zero

Dicas

0 / 3

Tempo-alvo
O(n · total)
Espaço-alvo
O(total)

Restrições

  • each card is used at most once and in full

Travou na ideia, e não no código? Mochila 0/1 explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado