##### Welcome to Subscribe On Youtube

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 empty list. You may return the integers in any order.

Example 1:

Input: finalSum = 12
Output: [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 = 7
Output: []
Explanation: There are no valid splits for the given finalSum.
Thus, we return an empty array.


Example 3:

Input: finalSum = 28
Output: [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 <= 1010

## 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;
}
};

• class Solution:
def maximumEvenSplit(self, finalSum: int) -> List[int]:
if finalSum % 2:
return []
i = 2
ans = []
while i <= finalSum:
ans.append(i)
finalSum -= i
i += 2
ans[-1] += finalSum
return ans

############

# 2178. Maximum Split of Positive Even Integers
# https://leetcode.com/problems/maximum-split-of-positive-even-integers/

class Solution:
def maximumEvenSplit(self, s: int) -> List[int]:
if s & 1: return []

res = []
x = 2

while x <= s:
res.append(x)
s -= x
x += 2

res[-1] += s

return res


• class Solution {
public List<Long> maximumEvenSplit(long finalSum) {
List<Long> ans = new ArrayList<>();
if (finalSum % 2 == 1) {
return ans;
}
for (long i = 2; i <= finalSum; i += 2) {
finalSum -= i;
}
return ans;
}
}

• func maximumEvenSplit(finalSum int64) []int64 {
ans := []int64{}
if finalSum%2 == 1 {
return ans
}
for i := int64(2); i <= finalSum; i += 2 {
ans = append(ans, i)
finalSum -= i
}
ans[len(ans)-1] += finalSum
return ans
}

• function maximumEvenSplit(finalSum: number): number[] {
const ans: number[] = [];
if (finalSum % 2 === 1) {
return ans;
}
for (let i = 2; i <= finalSum; i += 2) {
ans.push(i);
finalSum -= i;
}
ans[ans.length - 1] += finalSum;
return ans;
}


• public class Solution {
public IList<long> MaximumEvenSplit(long finalSum) {
IList<long> ans = new List<long>();
if (finalSum % 2 == 1) {
return ans;
}
for (long i = 2; i <= finalSum; i += 2) {
finalSum -= i;
}
ans[ans.Count - 1] += finalSum;
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;
}
};

• class Solution:
def maximumEvenSplit(self, finalSum: int) -> List[int]:
if finalSum % 2:
return []
i = 2
ans = []
while i <= finalSum:
ans.append(i)
finalSum -= i
i += 2
ans[-1] += finalSum
return ans

############

# 2178. Maximum Split of Positive Even Integers
# https://leetcode.com/problems/maximum-split-of-positive-even-integers/

class Solution:
def maximumEvenSplit(self, s: int) -> List[int]:
if s & 1: return []

res = []
x = 2

while x <= s:
res.append(x)
s -= x
x += 2

res[-1] += s

return res


• class Solution {
public List<Long> maximumEvenSplit(long finalSum) {
List<Long> ans = new ArrayList<>();
if (finalSum % 2 == 1) {
return ans;
}
for (long i = 2; i <= finalSum; i += 2) {
finalSum -= i;
}
return ans;
}
}

• func maximumEvenSplit(finalSum int64) []int64 {
ans := []int64{}
if finalSum%2 == 1 {
return ans
}
for i := int64(2); i <= finalSum; i += 2 {
ans = append(ans, i)
finalSum -= i
}
ans[len(ans)-1] += finalSum
return ans
}

• function maximumEvenSplit(finalSum: number): number[] {
const ans: number[] = [];
if (finalSum % 2 === 1) {
return ans;
}
for (let i = 2; i <= finalSum; i += 2) {
ans.push(i);
finalSum -= i;
}
ans[ans.length - 1] += finalSum;
return ans;
}


• public class Solution {
public IList<long> MaximumEvenSplit(long finalSum) {
IList<long> ans = new List<long>();
if (finalSum % 2 == 1) {
return ans;
}
for (long i = 2; i <= finalSum; i += 2) {
finalSum -= i;
}
ans[ans.Count - 1] += finalSum;
return ans;
}
}


## Discuss

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