贪心拆分

lc2178

贪心

“把偶数拆成最多不同偶数相加”：

先从2开始挨个加不同偶数，最后把剩下的数补到最后一个数上。

class Solution {
typedef long long ll;
public:
vector<long long> maximumEvenSplit(long long finalSum) {
if(finalSum%2LL) return {}; // 奇数直接返回空
vector<ll> ret;
ll sum = 0,num = 2; // 从最小的偶数2开始取
while(sum + num <= finalSum) {
ret.push_back(num);
sum += num;
num += 2; // 取下一个不同的偶数
}
// 补上剩余的差值
if(sum < finalSum)
ret.back() += (finalSum - sum);

return ret;
}
};

dfs tle

class Solution {
typedef long long ll;
public:
vector<long long> maximumEvenSplit(long long s) {
if (s%2) return {};
vector<ll> b, p;
function<void(ll, ll)> dfs = [&](ll l, ll r) {
if (!r) {
if (p.size() > b.size()) b = p;
return;
}
for (ll n = l + 2; n <= r; n += 2) {
p.push_back(n);
dfs(n, r - n);
p.pop_back();
}
};
dfs(0, s);
return b;
}
};