Formatted question description: https://leetcode.ca/all/2178.html

# 2178. Maximum Split of Positive Even Integers (Medium)

You are given an integer `finalSum`

. Split it into a sum of a **maximum** number of **unique** positive even integers.

- For example, given
`finalSum = 12`

, the following splits are**valid**(unique positive even integers summing up to`finalSum`

):`(2 + 10)`

,`(2 + 4 + 6)`

, and`(4 + 8)`

. Among them,`(2 + 4 + 6)`

contains the maximum number of integers. Note that`finalSum`

cannot be split into`(2 + 2 + 4 + 4)`

as all the numbers should be unique.

Return *a list of integers that represent a valid split containing a maximum number of integers*. If no valid split exists for

`finalSum`

, return *an*. You may return the integers in

**empty**list**any**order.

**Example 1:**

Input:finalSum = 12Output:[2,4,6]Explanation:The following are some valid splits:`(2 + 10)`

,`(2 + 4 + 6)`

, and`(4 + 8)`

. (2 + 4 + 6) has the maximum number of integers, which is 3. Thus, we return [2,4,6]. Note that [2,6,4], [6,2,4], etc. are also accepted.

**Example 2:**

Input:finalSum = 7Output:[]Explanation:There are no valid splits for the given finalSum. Thus, we return an empty array.

**Example 3:**

Input:finalSum = 28Output:[6,8,2,12]Explanation:The following are some valid splits:`(2 + 26)`

,`(6 + 8 + 2 + 12)`

, and`(4 + 24)`

.`(6 + 8 + 2 + 12)`

has the maximum number of integers, which is 4. Thus, we return [6,8,2,12]. Note that [10,2,4,12], [6,2,4,16], etc. are also accepted.

**Constraints:**

`1 <= finalSum <= 10`

^{10}

## Solution 1. Backtracking

If `finalSum`

is odd, return empty array.

Otherwise, we keep trying subtracting `2, 4, 6, 8, ...`

from `finalSum`

via backtracking.

```
// OJ: https://leetcode.com/problems/maximum-split-of-positive-even-integers/
// Time: O(sqrt(N))
// Space: O(sqrt(N))
class Solution {
public:
vector<long long> maximumEvenSplit(long long s) {
if (s % 2) return {};
vector<long long> ans;
function<bool(long, long)>dfs = [&](long i, long target) {
if (target == 0) return true;
if (target < i) return false;
ans.push_back(i);
if (dfs(i + 2, target - i)) return true; // use `i`
ans.pop_back();
return dfs(i + 2, target); // skip `i`
};
dfs(2, s);
return ans;
}
};
```

## Solution 2. Greedy

In solution 1, in fact we only backtrack at most once.

We can keep trying subtracting `2, 4, 6, 8, ...`

from `finalSum`

. We stop the loop when subtracting the current number `i`

is invalid – `s - i < i + 2`

(the reminder after the subtraction is less than the next even number). And we push the reminder into the answer.

```
// OJ: https://leetcode.com/problems/maximum-split-of-positive-even-integers/
// Time: O(sqrt(N))
// Space: O(1)
class Solution {
public:
vector<long long> maximumEvenSplit(long long s) {
if (s % 2) return {};
vector<long long> ans;
for (int i = 2; s - i >= i + 2; i += 2) {
ans.push_back(i);
s -= i;
}
ans.push_back(s);
return ans;
}
};
```

## Discuss

https://leetcode.com/problems/maximum-split-of-positive-even-integers/discuss/1783586