İçeriğe geç

Tam tutar için hediye kartları

Kolay#0-1-knapsack#subset-sum~20 dk

Görev tanımı

Problem

cards'taki değerlere sahip hediye kartların var ve her kart en fazla bir kez kullanılabilir. Bir kart tamamen kullanılmalı. Kartlardan bazılarının toplamı tam olarak total ediyorsa True, değilse False döndür.

Örnekler

Input:  cards = [3, 34, 4, 12, 5, 2], total = 9
Output: True
Neden: 4 + 5 = 9
Input:  cards = [3, 34, 4, 12, 5, 2], total = 30
Output: False
Neden: küçük kartların toplamı yalnız 26, 34'lük kart da tek başına zaten fazla
Input:  cards = [7], total = 0
Output: True
Neden: edge case: hiç kart kullanmamak tam olarak sıfır öder

İpuçları

0 / 3

Hedef zaman
O(n · total)
Hedef alan
O(total)

Kısıtlar

  • each card is used at most once and in full

Kodda değil de fikirde mi takıldın? 0/1 knapsack bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case