寻找数组等规模子集的最接近和组合及Python实现

问题背景 #

给定元素个数为偶数的数组，需将其划分为两个元素数量相等的子集，找出所有满足两个子集和尽可能接近的组合（优先和完全相等的情况）。例如数组[2,4,6,10,8,7,4,5]，需找出所有4元素子集，使其与对应的另一个4元素子集的和差最小（示例中和相等的情况是最优解）。

实现思路 #

1. 确定子集大小：数组长度为n，每个子集需包含k = n//2个元素。
2. 计算目标和：数组总和为total_sum，理想的子集和为target = total_sum // 2，我们需要找到所有k元素组合中，和最接近target的集合。
3. 生成所有可能的k元素组合，记录每个组合的和。
4. 筛选出与target差值最小的组合集合，同时去重（避免因数组重复元素导致的相同子集重复输出）。
5. 输出每个有效组合及其对应的互补子集，展示两者的和。

代码示例 #

import itertools

def find_balanced_subsets(nums):
    n = len(nums)
    if n % 2 != 0:
        raise ValueError("数组元素个数必须为偶数")
    k = n // 2
    total_sum = sum(nums)
    target = total_sum // 2

    # 生成所有k元素组合，并记录每个组合的和
    sum_to_combinations = {}
    for combo in itertools.combinations(nums, k):
        combo_sum = sum(combo)
        if combo_sum not in sum_to_combinations:
            sum_to_combinations[combo_sum] = []
        # 将组合排序后存入，方便后续去重
        sorted_combo = tuple(sorted(combo))
        sum_to_combinations[combo_sum].append(sorted_combo)

    # 找出与target差值最小的和值
    min_diff = float('inf')
    best_sums = []
    for s in sum_to_combinations:
        diff = abs(s - target)
        if diff < min_diff:
            min_diff = diff
            best_sums = [s]
        elif diff == min_diff:
            best_sums.append(s)

    # 收集所有最优组合，去重
    unique_combos = set()
    for s in best_sums:
        for combo in sum_to_combinations[s]:
            unique_combos.add(combo)

    # 输出结果
    print(f"数组总和: {total_sum}, 理想子集和: {target}, 最小差值: {min_diff}")
    print("所有最优划分组合:")
    for idx, combo in enumerate(unique_combos, 1):
        complement = nums.copy()
        # 移除组合中的元素（处理重复元素）
        for num in combo:
            complement.remove(num)
        complement_sum = sum(complement)
        combo_sum = sum(combo)
        print(f"组合{idx}:")
        print(f"  子集A: {list(combo)}, 和为 {combo_sum}")
        print(f"  子集B: {complement}, 和为 {complement_sum}")
        print("---")

# 测试示例
nums = [2,4,6,10,8,7,4,5]
find_balanced_subsets(nums)

代码说明 #

• 组合生成：使用itertools.combinations生成所有k元素的组合，确保每个组合的元素数量符合要求。
• 去重处理：将组合排序后转为元组存入集合，避免因数组中重复元素导致的相同子集被多次统计（比如示例中的两个4，不同位置的选择会生成元素相同的组合，视为同一划分）。
• 最优筛选：通过计算每个组合和与target的差值，找到差值最小的所有组合，优先输出和完全相等的情况。
• 互补子集生成：通过从原数组中移除当前组合的元素，得到对应的另一个子集，确保元素数量正确。

性能提示 #

当数组元素数量较大（如n > 20）时，生成所有组合的时间复杂度会显著上升（组合数为C(n, n/2)）。此时可以考虑使用动态规划优化，记录能组成特定和的k元素组合，但实现复杂度会更高。对于中小规模的数组，上述代码足够高效。

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