# Maximum Split of Positive Even Integers **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximum-split-of-positive-even-integers) Canonical: https://scaleengineer.com/dsa/problems/maximum-split-of-positive-even-integers **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking) --- ## Problem 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`): `(12)`, `(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 valid splits: `(12)`, `(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 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` # Approaches ## Backtracking / Brute Force This approach attempts to find the solution by exploring all possible combinations of unique positive even integers that sum up to `finalSum`. It uses a recursive function to build potential splits. At each step, the function decides which even number to add next and recurses with the remaining sum. This brute-force method will eventually find the split with the maximum number of elements by checking every valid partition. **Time:** O(2^N) or higher (exponential) · **Space:** O(sqrt(finalSum)) **Pros:** It's a straightforward brute-force method that is guaranteed to find the optimal solution if given enough time. **Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.; The recursion depth can be large, potentially leading to a stack overflow for very large `finalSum`, although the number of elements is limited by `sqrt(finalSum)`. ### Explanation The backtracking algorithm systematically generates all partitions of `finalSum` into unique, positive, even integers. We define a recursive helper function that takes the remaining sum to be made, the starting even number to consider (to enforce uniqueness and order), and the current list of numbers in the split. The function has two main cases: 1. **Base Case:** If the remaining sum is zero, it means we've successfully found a valid split. We then check if this new split has more numbers than the best one we've found so far. If it does, we update our answer. 2. **Recursive Step:** We iterate through all possible even numbers `i` that can be added (i.e., `i <= remainingSum`). For each `i`, we add it to our current split and make a recursive call for the new remaining sum (`remainingSum - i`). To ensure the numbers are unique, the next recursive call can only use even numbers greater than `i`. After the recursive call returns, we backtrack by removing `i` to explore other possibilities. While correct in theory, this approach is computationally expensive as the number of partitions can grow exponentially with `finalSum`. ```java // NOTE: This is a conceptual implementation and will Time Limit Exceed. class Solution { List maxSplit = new ArrayList<>(); public List maximumEvenSplit(long finalSum) { if (finalSum % 2 != 0) { return new ArrayList<>(); } find(finalSum, 2L, new ArrayList<>()); return maxSplit; } private void find(long target, long startNum, List currentSplit) { if (target == 0) { if (currentSplit.size() > maxSplit.size()) { maxSplit = new ArrayList<>(currentSplit); } return; } if (target < startNum) { return; } // Explore all possible next numbers for (long i = startNum; i <= target; i += 2) { currentSplit.add(i); find(target - i, i + 2, currentSplit); currentSplit.remove(currentSplit.size() - 1); // Backtrack } } } ``` ### Algorithm 1. Handle the base case: if `finalSum` is odd, it's impossible to form it from even numbers, so return an empty list. 2. Use a recursive backtracking function, say `solve(remainingSum, startEvenNum, currentSplit)`, to explore all possibilities. 3. `remainingSum`: The target sum left to achieve. 4. `startEvenNum`: The next smallest even number we can consider adding to ensure uniqueness. 5. `currentSplit`: The list of numbers forming the current partial solution. 6. **Base Case:** If `remainingSum` is 0, a valid split has been found. Compare its size with the maximum size found so far and update the global result if it's larger. 7. **Recursive Step:** For each even number `i` starting from `startEvenNum` up to `remainingSum`: a. Add `i` to `currentSplit`. b. Make a recursive call: `solve(remainingSum - i, i + 2, currentSplit)`. c. Backtrack by removing `i` from `currentSplit` to explore other branches. 8. This process explores all possible partitions into unique even numbers, and we keep the one with the most elements. ## Greedy Approach A greedy approach is the most efficient way to solve this problem. The core idea is that to maximize the number of elements in the sum, we should use the smallest possible unique positive even integers. We can iteratively build our split by adding 2, 4, 6, 8, and so on, until we can no longer add the next even number without exceeding `finalSum`. The final remaining amount is then consolidated into the largest number in our split to maintain the sum and uniqueness. **Time:** O(sqrt(finalSum)) - The `while` loop iterates `k` times, where the sum of the first `k` even numbers (`~k^2`) is on the order of `finalSum`. · **Space:** O(sqrt(finalSum)) - to store the resulting list of numbers. The number of elements `k` in the list is such that `k^2` is approximately `finalSum`. **Pros:** Highly efficient with a time complexity of O(sqrt(finalSum)).; Simple to implement and understand.; Guaranteed to produce a correct result with the maximum number of integers. **Cons:** The correctness of the greedy choice is not immediately obvious without a proof or strong intuition. ### Explanation This method is based on a greedy strategy. We start by checking if `finalSum` is even. If not, we return an empty list as a sum of even numbers cannot be odd. To get the maximum number of terms, we should pick the smallest unique positive even numbers: 2, 4, 6, ... We iteratively add these numbers to a list and subtract them from a running `remainingSum` (initialized to `finalSum`). We continue this process as long as the next even number to be added is not greater than the `remainingSum`. When the loop terminates, the `remainingSum` will hold the leftover amount. This leftover amount is guaranteed to be even. Because it was not large enough to form a new unique even number in our sequence, we simply add it to the last number we placed in our list. This ensures the sum is correct, all numbers are positive and even, and because we add it to the largest element, uniqueness is preserved. For example, if `finalSum = 28`: - Add 2, `remainingSum` = 26. List: `[2]` - Add 4, `remainingSum` = 22. List: `[2, 4]` - Add 6, `remainingSum` = 16. List: `[2, 4, 6]` - Add 8, `remainingSum` = 8. List: `[2, 4, 6, 8]` - Next even number is 10, which is greater than `remainingSum` (8). Stop. - The leftover is 8. Add it to the last element (8). The last element becomes `8 + 8 = 16`. - Final list: `[2, 4, 6, 16]`. Sum = 28. All unique, positive, even. ```java import java.util.ArrayList; import java.util.List; class Solution { public List maximumEvenSplit(long finalSum) { // If finalSum is odd, it's impossible to split it into even integers. if (finalSum % 2 != 0) { return new ArrayList<>(); } List result = new ArrayList<>(); long currentEven = 2; long remainingSum = finalSum; // Greedily take the smallest unique even numbers as long as the remainder // is large enough to accommodate the current number. while (currentEven <= remainingSum) { result.add(currentEven); remainingSum -= currentEven; currentEven += 2; } // The remainingSum is what's left. Since we couldn't form a new unique // even number with it, we add it to the largest number we've already added // to maintain the total sum and uniqueness. if (remainingSum > 0) { long lastElement = result.remove(result.size() - 1); result.add(lastElement + remainingSum); } return result; } } ``` ### Algorithm 1. First, check if `finalSum` is odd. If so, a split is impossible, so return an empty list. 2. Initialize an empty list `result` to store the integers. 3. Initialize a variable `currentEven` to 2, representing the smallest positive even integer. 4. Initialize `remainingSum` to `finalSum`. 5. Loop as long as the next number to add (`currentEven`) is less than or equal to the `remainingSum`. a. Add `currentEven` to the `result` list. b. Subtract `currentEven` from `remainingSum`. c. Increment `currentEven` by 2 to get the next unique even number. 6. After the loop terminates, the `remainingSum` will be a positive even integer that was too small to be the next term in the sequence (i.e., `remainingSum < currentEven`). 7. To ensure the total sum is correct and all numbers are unique, add this `remainingSum` to the last (and largest) number already in the `result` list. 8. Return the `result` list. # Solutions ### CSharp ```csharp 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) { ans.Add(i); finalSum -= i; } ans[ans.Count - 1] += finalSum; return ans; } } ``` ### Java ```java class Solution { public List maximumEvenSplit(long finalSum) { List ans = new ArrayList<>(); if (finalSum % 2 == 1) { return ans; } for (long i = 2; i <= finalSum; i += 2) { ans.add(i); finalSum -= i; } ans.add(ans.remove(ans.size() - 1) + finalSum); return ans; } } ``` ### CPP ```cpp class Solution { public: vector maximumEvenSplit(long long finalSum) { vector ans; if (finalSum % 2) return ans; for (long long i = 2; i <= finalSum; i += 2) { ans.push_back(i); finalSum -= i; } ans.back() += finalSum; return ans; } }; ``` ### Python ```python 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 ```