最接近目标值的子序列和

问题解法总结

数组的和不大

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

例题

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

数组长度不大

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

步骤：

1. 将数组分成两部分
2. 枚举出两个数组的所有子序列和，并排序
3. 有序的 twoSum 问题 => 双指针

例题

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