[Python3] top-down dp
\n\nclass Solution:\n    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n        toppingCosts *= 2\n        \n       
\n```\nclass Solution:\n    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n        toppingCosts *= 2\n        \n        @cache\n        def fn(i, x):\n            """Return sum of subsequence of toppingCosts[i:] closest to x."""\n            if x < 0 or i == len(toppingCosts): return 0\n            return min(fn(i+1, x), toppingCosts[i] + fn(i+1, x-toppingCosts[i]), key=lambda y: (abs(y-x), y))\n        \n        ans = inf\n        for bc in baseCosts: \n            ans = min(ans, bc + fn(0, target - bc), key=lambda x: (abs(x-target), x))\n        return ans \n```\nTime complexity `O(MNV)`\n\nEdited on 2/28/2021\n\nAdding the version by @lenchen1112\n```\nclass Solution:\n    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n        \n        @cache\n        def fn(i, cost):\n            """Return sum of subsequence closest to target."""\n            if cost >= target or i == len(toppingCosts): return cost\n            return min(fn(i+1, cost), fn(i+1, cost+toppingCosts[i]), key=lambda x: (abs(x-target), x))\n        \n        ans = inf\n        toppingCosts *= 2\n        for cost in baseCosts: \n            ans = min(ans, fn(0, cost), key=lambda x: (abs(x-target), x))\n        return ans \n```\n\nAdding binary search implementation\n```\nclass Solution:\n    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n        top = {0}\n        for x in toppingCosts*2: \n            top |= {x + xx for xx in top}\n        top = sorted(top)\n        \n        ans = inf \n        for bc in baseCosts: \n            k = bisect_left(top, target - bc)\n            if k < len(top): ans = min(ans, bc + top[k], key=lambda x: (abs(x-target), x))\n            if k: ans = min(ans, bc + top[k-1], key=lambda x: (abs(x-target), x))\n        return ans \n```\nTime complexity `O(N*2^(2N) + MN)`
['Python3']