MediumNo. 1774
Closest Dessert Cost — LeetCode 1774 Python Solution
- Pattern
- Backtracking
- Topics
- Array, Dynamic Programming, Backtracking
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You would like to make dessert and are preparing to buy the ingredients. You have n ice cream base flavors and m types of toppings to choose from.
Example
- Input
- baseCosts = [1,7], toppingCosts = [3,4], target = 10
- Output
- 10
- Explanation
- Consider the following combination (all 0-indexed):
Python solution
class Solution:
def closestCost(
self, baseCosts: List[int], toppingCosts: List[int], target: int
) -> int:
def dfs(i, t):
if i >= len(toppingCosts):
arr.append(t)
return
dfs(i + 1, t)
dfs(i + 1, t + toppingCosts[i])
arr = []
dfs(0, 0)
arr.sort()
d = ans = inf
# 选择一种冰激淋基料
for x in baseCosts:
# 枚举子集和
for y in arr:
# 二分查找
i = bisect_left(arr, target - x - y)
for j in (i, i - 1):
if 0 <= j < len(arr):
t = abs(x + y + arr[j] - target)
if d > t or (d == t and ans > x + y + arr[j]):
d = t
ans = x + y + arr[j]
return ansComplexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1774. Closest Dessert Cost is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0473 | Matchsticks to Square | Medium |
| 0494 | Target Sum | Medium |
| 0526 | Beautiful Arrangement | Medium |
| 0638 | Shopping Offers | Medium |
| 0698 | Partition to K Equal Sum Subsets | Medium |
| 0773 | Sliding Puzzle | Hard |
Frequently asked questions
- How hard is LeetCode 1774. Closest Dessert Cost?
LeetCode 1774. Closest Dessert Cost is rated Medium on LeetCode.
- What topics does LeetCode 1774. Closest Dessert Cost cover?
LeetCode 1774. Closest Dessert Cost is tagged Array, Dynamic Programming and Backtracking on LeetCode.