Gift Cards for an Exact Total
Problem
You hold gift cards with the values in cards, and each card can be used at most once. A card must be used in full. Return True if some of the cards add up to exactly total, otherwise False.
Examples
Input: cards = [3, 34, 4, 12, 5, 2], total = 9
Output: True
Why: 4 + 5 = 9Input: cards = [3, 34, 4, 12, 5, 2], total = 30
Output: False
Why: the small cards add up to only 26, and the 34 card alone is already too muchInput: cards = [7], total = 0
Output: True
Why: edge case, using no cards pays exactly zeroHints
0 / 3
Trying every subset of cards is 2 to the power n. The only thing that matters about a group of cards is the total it reaches.
Track which totals from 0 up to the target can be reached with the cards seen so far. Adding one card makes a total t reachable if t minus that card was reachable before this card.
Keep a list of booleans indexed by total, with index 0 set to True. For each card, walk the totals from the target down to the card's value and mark t reachable when t minus the card is. Walking downward stops a card from being used twice.
Solution
This is the 0/1 knapsack with a yes-or-no answer, often called subset sum. reachable[t] says whether some of the cards seen so far add up to exactly t, and each new card either stays out, leaving the entry as it was, or goes in, copying the answer from reachable[t - card]. The inner loop runs from high totals to low so that reachable[t - card] still describes the cards before this one, which is what keeps each card to a single use. Time is O(n · total) and space is O(total).
def exact_total(cards, total):
reachable = [False] * (total + 1)
reachable[0] = True # zero is paid with no cards
for card in cards:
for t in range(total, card - 1, -1): # downward: each card used at most once
if reachable[t - card]:
reachable[t] = True
return reachable[total]
print(exact_total([3, 34, 4, 12, 5, 2], 9)) # -> True
print(exact_total([3, 34, 4, 12, 5, 2], 30)) # -> False
print(exact_total([7], 0)) # -> TrueStuck on the idea rather than the code? 0/1 Knapsack covers it.