You are given an integer finalSum. Split it into a sum of a maximum number of unique positive even integers.
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 <= 1010Problem Overview: Given an integer finalSum, return the maximum number of unique positive even integers whose sum equals that value. If finalSum is odd, no valid split exists. The challenge is constructing the largest set of distinct even numbers while keeping the total exactly equal to the target.
Approach 1: Recursive Divide and Conquer (Backtracking) (Time: O(2^n), Space: O(n))
This approach explores combinations of even numbers using recursion. Start from the smallest even number (2) and recursively decide whether to include the next even value in the split. The recursion tracks the remaining sum and the current list of chosen numbers. If the remaining value becomes zero, a valid split is found. Because the algorithm tries many combinations, the branching factor grows quickly and results in exponential time complexity. This method is useful for understanding the search space and practicing recursion with backtracking, but it is not efficient for large inputs.
Approach 2: Iterative Dynamic Programming (Time: O(n^2), Space: O(n))
Dynamic programming builds solutions for smaller sums and uses them to construct larger ones. Create a DP array where each index represents whether a sum can be formed using unique even numbers. For each even number 2, 4, 6..., update states by checking whether adding the current number creates a valid new sum. While this avoids exploring every recursive path, it still requires iterating through many possible states and combinations. The DP approach works well when you want to explicitly track achievable sums and demonstrate subset-style reasoning often used in dynamic programming problems.
Approach 3: Greedy Mathematical Construction (Time: O(sqrt(n)), Space: O(1) excluding output)
The optimal insight comes from greedy algorithms. To maximize the count of distinct even numbers, always take the smallest possible unused even integer. Start with 2, then 4, 6, and keep subtracting from finalSum. Once the remaining value becomes smaller than the next candidate even number, add the leftover to the last element in the list. This keeps all numbers unique while preserving the total sum. If finalSum is odd, return an empty list immediately. Because the sequence of even numbers grows linearly while their sum grows quadratically, the loop runs roughly sqrt(finalSum) times, making it extremely efficient.
Recommended for interviews: The greedy construction is the expected solution. It demonstrates mathematical reasoning and efficient use of the problem constraints. Discussing the recursive search first shows you understand the full solution space, but implementing the greedy approach proves you can identify the optimal strategy quickly.
This approach involves breaking down the problem recursively into smaller subproblems, solving each subproblem independently, and combining their results. It leverages the divide and conquer paradigm which is efficient for many types of problems.
The recursive solution divides the array into two halves and solves each half independently. It then combines the results to form the final answer.
Time Complexity: O(n log n) for a balanced division.
Space Complexity: O(log n) due to recursion stack space.
This approach uses an iterative dynamic programming method where we compute results in a bottom-up manner. It's especially useful when recursion might lead to stack overflow and provides an iterative solution with the same logic.
Using a DP array, the cumulative results from the array calculation are stored iteratively. This prevents recursive stack overflow and uses previous results for new calculations.
Time Complexity: O(n)
Space Complexity: O(n) due to the DP array.
If finalSum is odd, it cannot be split into the sum of several distinct positive even integers, so we directly return an empty array.
Otherwise, we can greedily split finalSum in the order of 2, 4, 6, cdots, until finalSum can no longer be split into a different positive even integer. At this point, we add the remaining finalSum to the last positive even integer.
The time complexity is O(\sqrt{finalSum}), and ignoring the space consumption of the answer array, the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Recursive Divide and Conquer | Time Complexity: O(n log n) for a balanced division. |
| Iterative Dynamic Programming | Time Complexity: O(n) |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Divide and Conquer (Backtracking) | O(2^n) | O(n) | When exploring all possible combinations or demonstrating recursion and search space exploration |
| Iterative Dynamic Programming | O(n^2) | O(n) | When modeling the problem as a subset-sum style DP and tracking reachable sums |
| Greedy Mathematical Construction | O(sqrt(n)) | O(1) | Best choice for production or interviews; constructs the maximum set directly |
2178. Maximum Split of Positive Even Integers || Biweekly Contest 72 || Leetcode 2178 • Bro Coders • 1,891 views views
Watch 9 more video solutions →Practice Maximum Split of Positive Even Integers with our built-in code editor and test cases.
Practice on FleetCode