Saltar al contenido

Tarjetas de regalo para un total exacto

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

La misión

Problema

Tienes tarjetas de regalo con los valores de cards, y cada tarjeta se puede usar como máximo una vez. Una tarjeta debe usarse completa. Devuelve True si algunas de las tarjetas suman exactamente total; si no, devuelve False.

Ejemplos

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é: las tarjetas pequeñas solo suman 26, y la tarjeta de 34 sola ya se pasa
Input:  cards = [7], total = 0
Output: True
Por qué: caso límite: no usar ninguna tarjeta paga exactamente cero

Pistas

0 / 3

Tiempo objetivo
O(n · total)
Espacio objetivo
O(total)

Restricciones

  • each card is used at most once and in full

¿Lo que te frena es la idea y no el código? Mochila 0/1 lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio