3

class Solution:
  # n: num of cards
  # m: total cost
  def giftCards(self, cardsCount, totalCost):
    return self.dfsHelper(totalCost, [10, 30, 50], 0, cardsCount)
    
  def dfsHelper(self, targetCost, denoms, denomStart, leftCardsCount):
    # base case
    if targetCost == 0 and leftCardsCount == 0:
      print(path)
      return 1
    elif targetCost < 0 or leftCardsCount <= 0:
      return 0
    # general case
    totalWays = 0
    for i in range(denomStart, len(denoms)):
      path.append(denoms[i])
      ways = self.dfsHelper(targetCost - denoms[i], denoms, i, leftCardsCount - 1)
      del path[-1]
      totalWays += ways
    return totalWays