[双向dfs]leetcode1755：最接近目标值的子序列和(hard)

目标值的子序列和(hard)"/>

[双向dfs]leetcode1755：最接近目标值的子序列和(hard)

题目：

题解：

由于 2^40 ≈ 10^12，这样直接dfs枚举每个数组值的话肯定会超时的，所以我们将数组一分为二，分别搜索两部分来降低时间复杂度。

算法步骤：

• 1）第一次搜索：我们枚举前半段数组的所有元素选或不选得到所有状态的子序列和 sum，然后将每个 sum 存入数组 q，并对数组 q 进行排序。
• 2）第二次搜索：尝试从后半段数组中选一些元素，找到后半段一个可行解 sum 后，然后我们二分查找数组 q，即从前半段中选一个子序列的和，然后二分找到小于等于 goal 的最大位置（sum+q[mid]<=goal mid的最大位置）。
• 3）当然我们要更新 res 的话，还要比较大于 goal 的最小位置，即最接近 goal 的位置，位于它的两侧。

时间复杂度： O ( 2 N / 2 ∗ l o g 2 N / 2 ) O(2^{N/2} * log2^{N/2}) O(2N/2∗log2N/2)= O ( N ∗ 2 N / 2 ) O(N*2^{N/2}) O(N∗2N/2)，空间复杂度： O ( 2 N / 2 ) O(2^{N/2}) O(2N/2)

代码如下：

// 2^20 < 2*1000*1000，所以数组大小开1e6
const int N = 2e6+10;int q[N];class Solution {
public:int n,cnt,goal,res;void dfs1(vector<int>& nums,int idx,int sum){// 找到一个可行解if(idx==(n+1)/2)// n向上取整，前半部分为[0,n/2]{q[cnt++]=sum;return;}// 枚举两种情况，一种是选上第idx个元素，另一种是不选第idx个元素dfs1(nums,idx+1,sum);dfs1(nums,idx+1,sum+nums[idx]);} void dfs2(vector<int>& nums,int idx,int sum){// 找到一个可行解if(idx==n)// 后半部分为[n/2+1,n-1]{int l=0,r=cnt-1;// 二分查找<=goal 的最大位置while(l<r){// 向上取整，避免 left 取不到 right 造成死循环int mid=(l+r+1)>>1;if(q[mid]+sum<=goal)l=mid;// mid满足check，向右逼近，mid可能就是目标值，所以l=midelse r=mid-1;// mid不满足check，向左逼近，mid不可能为目标值，所以r=mid-1}// 最后找到的元素为最接近goal的res=min(res,abs(q[r]+sum-goal));// 若r有下一个元素，那么我们最近goal的元素要么在 <=goal 的最大位置产生，要么在 >goal 的最小位置产生// 所以每次更新res时，注意这两个位置if(r+1<cnt)res=min(res,abs(q[r+1]+sum-goal));return;}// 枚举两种情况，一种是选上第idx个元素，另一种是不选第idx个元素dfs2(nums,idx+1,sum);dfs2(nums,idx+1,sum+nums[idx]);}// 题解：双向dfs，dfs1枚举2^20中选法，然后排序前半段得到的子序列和数组，然后再枚举后半段的子序列，二分前半段的子序列和数组，使得前半段的子序列和与后半段的子序列和相加的结果接近goalint minAbsDifference(vector<int>& nums, int _goal) {n=nums.size(),cnt=0,goal=_goal,res=INT_MAX;// 先搜索前一半，给搜索完的数组排个序，便于在搜索后一半数组的时候进行二分dfs1(nums,0,0);sort(q,q+cnt);// 搜索后一半dfs2(nums,(n+1)/2,0);return res;}
};