Python DFS solution

  • 2

    Just recursively try every possible combination.
    Compare how much it costs among retail price (no offer) and using each offer.
    Terminate when
    (1) The condition met: return accumulated value
    (2) The condition violated: not an option, hence infinity

    def shoppingOffers(self, price, special, needs):
            def dfs(remain, acc):
                if all(x == 0 for x in remain):
                    return acc
                elif any(x < 0 for x in remain):
                    return float('inf')
                ans = sum(map(lambda x, y: x*y, remain, price))
                for spc in special:
                    ans = min(ans, dfs(map(lambda x, y: x-y, remain, spc[:-1]), spc[-1]))                
                return ans+acc
            return dfs(needs, 0)

  • 0

    Neat solution, thank you!

  • 1

    The testcases are weak. This solution TLEs on this case:

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.