1774.最接近目标价格的甜点成本

https://leetcode.cn/problems/closest-dessert-cost

方法一：回溯

暴力回溯，设 baseCosts 长度为 n，toppingCosts 长度为 m，则时间复杂度 $O(n \times 3^m)$，空间复杂度 $O(m)$。

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
	ans, m := 10001, len(toppingCosts)
	// 此处使 ans 为 baseCosts 的最小值的原因是：
	// 若 ans ≥ target，则无论我们是否添加配料都不会使甜品制作的开销与目标价格 target 的距离缩小，所以此时直接返回此最小的基料开销即可
	for _, v := range baseCosts {
		ans = min(v, ans)
	}
	var backtrack func(start, sum int)
	backtrack = func(start, sum int) {
		if abs(ans-target) >= abs(sum-target) {
			if abs(ans-target) > abs(sum-target) {
				ans = sum
			} else {
				ans = min(ans, sum)
			}
		} else if abs(ans-target) < sum-target {
			return
		}
		if start >= m {
			return
		}

		backtrack(start+1, sum)
		backtrack(start+1, sum+toppingCosts[start])
		backtrack(start+1, sum+toppingCosts[start]*2)
	}
	for _, v := range baseCosts {
		backtrack(0, v)
	}
	return ans
}