如何将整数数组划分为两个和相等的子数组并返回划分结果

这个需求属于经典的等和子集问题，完全可以实现，核心规则是拆分后的两个子数组不重叠、覆盖原数组全部元素、元素和相等。只要找到一个和为原数组总数值一半的子集，剩余元素自然构成另一个符合要求的子数组。

原代码的问题 #

• 仅记录了可凑出的和值，没有追踪凑出对应和使用了哪些元素，无法避免同一个元素被重复选取的问题
• 命中目标和时直接拼接数值t和当前元素，t只是和的数值不是元素列表，无法区分这个数值是单个元素还是多个元素求和得到的，因此会出现[4,4]这类不符合要求的结果
• 目标和计算使用普通除法得到浮点数，整数运算场景下存在精度隐患，应该使用整数除法

修正后的可运行代码 #

实现逻辑用动态规划记录每个可凑出的和对应的元素索引集合，从根源避免元素重复选取，找到符合要求的子集后直接返回两个子数组：

def partition(nums):
    total_sum = sum(nums)
    # 总和为奇数时不可能拆成两个和相等的整数子集
    if total_sum % 2 != 0:
        return "Not possible"
    target = total_sum // 2
    # dp结构：key为可凑出的和，value为凑出该和用到的元素下标集合
    dp = {0: set()}

    for idx, num in enumerate(nums):
        temp_update = {}
        # 遍历已有的可凑出和，尝试加入当前元素生成新的和
        for current_sum, used_idx in dp.items():
            new_sum = current_sum + num
            # 已经记录过的和无需重复处理
            if new_sum not in dp and new_sum not in temp_update:
                new_used = used_idx.copy()
                new_used.add(idx)
                # 找到目标和，直接拆分出两个子数组返回
                if new_sum == target:
                    sub1 = [nums[i] for i in new_used]
                    sub2 = [nums[i] for i in range(len(nums)) if i not in new_used]
                    return sub1, sub2
                temp_update[new_sum] = new_used
        # 将本轮新生成的和更新到dp中
        dp.update(temp_update)
    
    # 遍历完所有元素仍未找到目标子集
    return "Not possible"

# 测试示例输入
nums = [1, 2, 3, 4, 6]
print(partition(nums))

运行上述代码，输入示例数组会输出合法的拆分结果，结果顺序可能为([2,6], [1,3,4])或([1,3,4], [2,6])，均满足和为8、无重复元素、覆盖全部原数组元素的要求。

该实现通过索引区分元素，即使数组中存在值相同的不同元素（比如输入[2,2]），也不会出现重复选取同一元素的问题。

内容的提问来源于stack exchange，提问作者Ravi Teja KNTS