LeetCode 2178：如何用循环实现正偶数的最大唯一拆分？

题目描述 #

给定一个整数finalSum，将其拆分为最多个唯一正偶数的和。返回包含最多整数的有效拆分列表；如果无法拆分（比如finalSum是奇数），返回空列表。返回的整数顺序不限。

示例：当finalSum = 12时，有效的拆分方式有[12]、[2,10]、[2,4,6]和[4,8]，其中[2,4,6]包含最多的整数。注意不能拆分为[2,2,4,4]，因为所有数字必须唯一。

约束条件：1 ≤ finalSum ≤ 10^10

我的尝试 #

我一开始想用嵌套for循环枚举组合，但只能处理最多两个数的情况，而且逻辑混乱，代码如下：

even = [2, 4, 6, 8, 10, 12, 14, 16]
finalSum = 16

current_sum = 0
current_comb = []
all_combs = []

for j in range(len(even)):
    
    current_comb.append(even[j])
    
    for k in range(j+1, len(even)):

        current_comb.append(even[k])

        print("current combination", current_comb)

        current_sum = sum(current_comb)
        print("current sum", current_sum)

        if current_sum == finalSum:
            print("sum = finalSum")
            # append to all combs
            all_combs.append(current_comb)
            current_comb = []
            
        elif current_sum > finalSum:
            print("current sum > final sum")
            # since array is sorted by ASC, even other value is going to be >, therefore pop the last 2 elements
            current_comb = current_comb[:-2]
            print("pop last 2 elements", current_comb)

现在我卡住了，不知道怎么扩展到更长的拆分，而且这种枚举方式显然没法处理10^10这么大的数。我偏好使用for或while循环来解决问题。

正确解法（基于for/while循环） #

首先明确两个核心点：

1. 若finalSum是奇数，直接返回空列表——奇数无法拆分为若干正偶数的和。
2. 要得到最多的唯一偶数，必须从最小的偶数开始累加（2、4、6...），用最少的数值占比换取最多的元素数量。当累加和即将超过finalSum时，把剩余的差值加到最后一个元素上，既保证总和正确，又不会出现重复元素。

代码实现（while循环版） #

def maximumEvenSplit(finalSum):
    if finalSum % 2 != 0:
        return []
    result = []
    current = 2
    remaining = finalSum
    while remaining >= current:
        result.append(current)
        remaining -= current
        current += 2
    # 把剩余值追加到最后一个元素，避免重复
    if remaining > 0:
        result[-1] += remaining
    return result

代码实现（for循环版） #

如果偏好for循环，可先计算最多能容纳的连续偶数个数，再处理剩余值：

def maximumEvenSplit(finalSum):
    if finalSum % 2 != 0:
        return []
    result = []
    remaining = finalSum
    current = 2
    # 计算最大连续偶数个数：解方程n*(n+1) ≤ finalSum/2
    max_count = int((-2 + (4 + 8 * finalSum)**0.5)//4)
    for _ in range(max_count):
        result.append(current)
        remaining -= current
        current += 2
    if remaining > 0:
        result[-1] += remaining
    return result

思路解释 #

• 先判断finalSum的奇偶性，奇数直接返回空。
• 从2开始依次累加偶数，直到下一个偶数大于剩余值，此时停止累加。
• 剩余值remaining必然小于下一个要加的偶数，将其加到最后一个元素上：因为最后一个元素是current-2，(current-2)+remaining < (current-2)+current，而之前的所有元素都小于current-2，因此不会出现重复。

比如finalSum=16：

1. 累加2、4、6后，剩余值为4，下一个偶数是8（4<8），循环停止。
2. 将剩余的4加到6上，得到[2,4,10]，这是元素最多的拆分之一。

原始代码的问题 #

• 枚举所有组合的时间复杂度是指数级的，完全无法处理10^10规模的输入。
• 嵌套循环只能处理最多两个元素的组合，无法生成更长的拆分序列，且列表重置逻辑会中断遍历，同时我们根本不需要收集所有组合，只需要找到元素最多的那个。

内容的提问来源于stack exchange，提问作者kms