最接近目标值的子序列和

问题解法总结

数组的和不大

如果数组长度特别大，但是数组的和不大 (sum <= 10^5)，我们可以使用背包问题的方式来解决，其中 dp[i] 表示是否能组成容量为 i 的背包。

例题

• lc1049. 最后一块石头的重量 II

数组长度不大

如果数组长度不大 (n <= 20)，但是数值特别大的话，使用枚举子集的方法。
如果数组长度接近 40，直接枚举 2^40 会超时，此时需要折半搜索。

步骤：

1. 将数组分成两部分
2. 枚举出两个数组的所有子序列和，并排序
3. 转化为有序的 two sum 问题，用双指针或二分查找

例题

• lc1755. 最接近目标值的子序列和
• lc5897. 将数组分成两个数组并最小化数组和的差