给你一个长度为2n的整数数组,需要将它分成两个长度为n的数组,分别求出两个数组的和,并最小化两个数组和之差的绝对值。nums中每个元素都需要放入两个数组之一,求最小的数组和之差。
1<=n<=15; -1E7<=nums[i]<=1E7
直接暴搜的话最坏时间复杂度是O(2^30)
,会TLE,可以使用双向dfs优化,每次dfs各搜一半,然后遍历其中一个集合,到另一个集合找最优解。时间复杂度降为O(2*2^15)
。
class Solution {
public:
int minimumDifference(vector<int>& nums) {
int n = nums.size();
vector<set<int>> st1(n), st2(n);
int sum = accumulate(nums.begin(), nums.end(), 0);
auto dfs = [&](auto self, int x, int R, int cnt, int cur, vector<set<int>> &st) -> void {
if (x == R) {
st[cnt].insert(2*cur);
return;
}
self(self, x+1, R, cnt, cur, st);
self(self, x+1, R, cnt+1, cur+nums[x], st);
};
dfs(dfs, 0, n/2, 0, 0, st1);
dfs(dfs, n/2, n, 0, 0, st2);
int ans = INT_MAX;
for (int k = 0; k < n/2; k++) {
int u = n/2 - k;
for (auto i : st1[k]) {
auto it = st2[u].lower_bound(sum-i);
if (it != st2[u].end()) {
ans = min(ans, abs(i + *it - sum));
}
if (it != st2[u].begin()) {
--it;
ans = min(ans, abs(i + *it - sum));
}
}
}
return ans;
}
};
标签:st2,lc2035,int,nums,dfs,数组,ans,最小化
From: https://www.cnblogs.com/chenfy27/p/18073839