LC-0638 Medium LeetCode

638. Shopping Offers

Array Dynamic Programming Backtracking Bit Manipulation Memoization Bitmask

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 52% Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Memoization, Bitmask

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Backtracking 14 min

Reference solution (spoiler · python)

# Time:  O(n * 2^n)
# Space: O(n)

class Solution(object):
    def shoppingOffers(self, price, special, needs):
        """
        :type price: List[int]
        :type special: List[List[int]]
        :type needs: List[int]
        :rtype: int
        """
        def shoppingOffersHelper(price, special, needs, i):
            if i == len(special):
                return sum(map(lambda x, y: x*y, price, needs))
            result = shoppingOffersHelper(price, special, needs, i+1)
            for j in xrange(len(needs)):
                needs[j] -= special[i][j]
            if all(need >= 0 for need in needs):
                result = min(result, special[i][-1] + shoppingOffersHelper(price, special, needs, i))
            for j in xrange(len(needs)):
                needs[j] += special[i][j]
            return result

        return shoppingOffersHelper(price, special, needs, 0)

Solution from kamyu104/LeetCode-Solutions · MIT