删除单个元素后判断数组能否划分为和相等的两个子集

问题描述 #

给定一个数值数组，判断是否可以删除其中一个元素后，将剩余元素分成两个子集，使两个子集的元素和相等。
示例：数组[1,2,3,4,5]删除1后，子集[2,5]和[3,4]的和都是7，返回true。

当前解法分析 #

你现在的思路是逐个删除元素，若剩余元素的总和是偶数，就用DP判断是否存在和为剩余和一半的子集。这种方法的时间复杂度是O(N²*target)（target最大为数组总和的一半），空间复杂度O(target)。瓶颈在于每次删除元素都要重新跑一次DP，导致时间开销翻倍。

更优解法：一次DP预处理，遍历验证 #

核心思路 #

我们可以只跑一次DP，算出整个数组的所有可能子集和，同时记录处理每个元素前的DP状态（也就是不包含该元素时的子集和情况）。之后遍历每个元素时，直接用预处理好的结果快速验证，不用重复计算DP。

具体逻辑推导：
设数组总和为S，对每个元素x：

1. 如果S - x是奇数，直接跳过——剩余元素总和是奇数，不可能分成两个和相等的子集。
2. 计算目标和T = (S - x) / 2，我们需要验证删除x后，剩余元素里能不能凑出和为T的子集，满足以下任意一种情况即可：
   • 情况1：不包含x的子集就能凑出T（对应处理x前的DP状态中T是可达的）。
   • 情况2：包含x的子集能凑出T + x（对应整个数组的DP状态中T + x是可达的）——去掉x后，剩余元素的和就是T。

复杂度分析 #

• 时间复杂度：O(N*target)，仅需一次DP遍历数组，后续每个元素的验证都是O(1)级别的状态查询。
• 空间复杂度：O(N*target)（需要保存每个元素处理前的DP状态），如果target不大，这种空间开销是可接受的；若要进一步优化空间，也可以在遍历元素时实时记录前置状态，将空间压缩到O(target)，但实现稍复杂。

代码示例 #

def can_split_after_remove(nums):
    total = sum(nums)
    n = len(nums)
    max_target = total // 2
    # 保存每个元素处理前的DP状态，prev_dps[i]代表处理第i个元素前的子集和可达情况
    prev_dps = []
    dp = [False] * (max_target + 1)
    dp[0] = True  # 空子集和为0
    
    for num in nums:
        # 先保存当前DP状态（还没处理当前元素，即不包含当前元素的状态）
        prev_dps.append(dp.copy())
        # 更新DP，加入当前元素的可能子集和
        for j in range(max_target, num - 1, -1):
            if dp[j - num]:
                dp[j] = True
    
    # 遍历每个元素，验证是否满足条件
    for i in range(n):
        x = nums[i]
        remaining_sum = total - x
        if remaining_sum % 2 != 0:
            continue
        target = remaining_sum // 2
        if target > max_target:
            continue
        
        # 情况1：不包含x的子集能凑出target
        case1 = prev_dps[i][target]
        # 情况2：包含x的子集能凑出target + x（即整个数组的DP中存在该和）
        case2 = dp[target + x] if (target + x) <= max_target else False
        
        if case1 or case2:
            return True
    return False

额外优化点 #

如果数组中存在重复元素，可以通过跳过重复元素减少验证次数；另外，如果target超过剩余元素的最大可能和，也可以直接跳过判断，进一步节省时间。

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