从洛谷P4799到LeetCode：手把手教你用折半搜索（Meet in the Middle）搞定大数组子集和问题

从洛谷P4799到LeetCode：手把手教你用折半搜索（Meet in the Middle）搞定大数组子集和问题

在算法竞赛和面试中，我们经常会遇到需要处理大数组子集和的问题。当数组规模达到40左右时，传统的暴力枚举方法时间复杂度高达O(2^40)，这显然是不可行的。折半搜索（Meet in the Middle）技术正是为解决这类问题而生的利器。

本文将带你从洛谷经典例题P4799出发，深入理解折半搜索的核心思想，并教你如何将这一技术迁移应用到LeetCode等面试题库中的类似问题上。无论你是正在准备技术面试的求职者，还是希望提升算法能力的开发者，掌握这一技巧都能让你在面对"大数组子集和"类问题时游刃有余。

1. 为什么需要折半搜索？

在处理子集和问题时，最直观的方法是枚举所有可能的子集。对于一个大小为n的数组，子集数量为2^n。当n=20时，2^20≈100万，这在现代计算机上尚可接受；但当n=40时，2^40≈1万亿，这已经完全超出了普通计算机的处理能力。

折半搜索通过将问题分成两个规模减半的子问题，将时间复杂度从O(2^n)降低到O(2^(n/2))。对于n=40的情况，2^20≈100万，这使得问题变得可解。

复杂度对比表：

2. 折半搜索的核心思想

折半搜索的基本原理可以概括为"分而治之"：

1. 分割阶段：将原始数组平均分成两部分（或接近平均）
2. 独立处理：分别计算两部分的所有可能子集和
3. 合并结果：通过组合两部分的中间结果得到最终解

以洛谷P4799为例，题目要求计算在预算m内能购买比赛门票的所有组合数。使用折半搜索的步骤如下：

def meet_in_the_middle(prices, budget): n = len(prices) half = n // 2 # 生成前半部分的所有子集和 left_sums = [] for mask in range(1 << half): total = 0 for i in range(half): if mask & (1 << i): total += prices[i] left_sums.append(total) # 生成后半部分的所有子集和 right_sums = [] for mask in range(1 << (n - half)): total = 0 for i in range(n - half): if mask & (1 << i): total += prices[half + i] right_sums.append(total) # 排序前半部分结果以便二分查找 left_sums.sort() count = 0 for right in right_sums: if right > budget: continue # 在left_sums中查找<= (budget - right)的元素数量 remaining = budget - right low, high = 0, len(left_sums) while low < high: mid = (low + high) // 2 if left_sums[mid] > remaining: high = mid else: low = mid + 1 count += low return count

提示：在实际编码中，可以使用更高效的位运算和内置二分查找函数（如Python的bisect）来优化性能。

3. 识别适用折半搜索的问题特征

不是所有子集和问题都适合使用折半搜索。以下是适用该技术的典型特征：

• 中等规模的输入：n通常在30-50之间（太小可以直接暴力，太大即使折半也不可行）
• 需要枚举所有可能组合：如子集和、子集计数等问题
• 组合条件可分解：问题的解可以表示为两个独立部分的某种组合

LeetCode中适用折半搜索的题目示例：

1. 2035. Partition Array Into Two Arrays to Minimize Sum Difference
2. 1755. Closest Subsequence Sum
3. 805. Split Array With Same Average

4. 折半搜索的优化技巧

4.1 提前终止

在某些问题中，我们可以在生成子集和的过程中提前终止不必要的计算。例如，在子集和问题中，如果当前累计和已经超过目标值，就可以停止进一步枚举。

def generate_sums(arr, max_sum): sums = [0] for num in arr: new_sums = [] for s in sums: if s + num <= max_sum: new_sums.append(s + num) sums += new_sums return sums

4.2 双指针合并

在某些情况下，我们可以使用双指针技术代替二分查找来合并两部分结果，这可以将合并阶段的时间复杂度从O(N log N)降低到O(N)。

def count_combinations(left, right, target): left.sort() right.sort() count = 0 l, r = 0, len(right) - 1 while l < len(left) and r >= 0: if left[l] + right[r] <= target: count += r + 1 l += 1 else: r -= 1 return count

4.3 哈希表加速

对于需要精确匹配的问题，可以使用哈希表存储一部分结果，快速查询另一部分结果是否存在对应的匹配项。

from collections import defaultdict def two_part_sum(nums, target): half = len(nums) // 2 left_sums = defaultdict(int) # 生成并存储左半部分的所有子集和 for mask in range(1 << half): total = sum(nums[i] for i in range(half) if mask & (1 << i)) left_sums[total] += 1 count = 0 # 检查右半部分的子集和 for mask in range(1 << (len(nums) - half)): total = sum(nums[half + i] for i in range(len(nums) - half) if mask & (1 << i)) count += left_sums.get(target - total, 0) return count

5. LeetCode实战：Partition Array Into Two Arrays to Minimize Sum Difference

让我们以LeetCode 2035题为例，演示如何应用折半搜索解决实际问题。题目要求将数组分成两部分，使两部分和的差最小。

解题步骤：

1. 将数组分成两半
2. 分别计算左右两半所有可能的大小为n/4的子集和（因为最终要分成两个等长或接近等长的子集）
3. 对于左边的每个子集和，在右边寻找能使其与总和/2最接近的子集和

def minimumDifference(nums): n = len(nums) total = sum(nums) half_n = n // 2 # 生成左半部分所有可能的大小为half_n的子集和 left = [[] for _ in range(half_n + 1)] for mask in range(1 << half_n): bits = bin(mask).count('1') if bits > half_n: continue sum_sub = sum(nums[i] for i in range(half_n) if mask & (1 << i)) left[bits].append(sum_sub) # 生成右半部分所有可能的大小为half_n的子集和 right = [[] for _ in range(half_n + 1)] for mask in range(1 << (n - half_n)): bits = bin(mask).count('1') if bits > half_n: continue sum_sub = sum(nums[half_n + i] for i in range(n - half_n) if mask & (1 << i)) right[bits].append(sum_sub) # 对右边的每个大小进行排序以便二分查找 for bits in range(half_n + 1): right[bits].sort() min_diff = float('inf') target = total / 2 # 对于左边选k个元素的情况，在右边选half_n - k个元素 for k in range(half_n + 1): for left_sum in left[k]: remaining = target - left_sum arr = right[half_n - k] # 在arr中找最接近remaining的值 idx = bisect.bisect_left(arr, remaining) for i in [idx - 1, idx]: if 0 <= i < len(arr): sum_right = arr[i] current_sum = left_sum + sum_right diff = abs(total - 2 * current_sum) if diff < min_diff: min_diff = diff if min_diff == 0: return 0 return min_diff

注意：在实际面试中，可能需要根据问题的具体约束条件调整上述代码。例如，如果数组长度很大但数值范围小，可以考虑动态规划等其他方法。

6. 常见陷阱与调试技巧

即使理解了折半搜索的原理，在实际编码中仍然可能遇到各种问题。以下是一些常见陷阱及解决方法：

陷阱1：错误的分割方式

问题：简单地将数组对半分割可能不是最优的，特别是当数组元素分布不均匀时。解决：可以尝试随机分割多次，或根据元素大小进行平衡分割。

陷阱2：内存溢出

问题：当n较大时（如n=40），存储所有子集和会消耗大量内存。解决：使用更紧凑的数据结构，或只存储必要的中间结果。

陷阱3：错误的合并逻辑

问题：在合并两部分结果时，可能忽略了一些边界条件。解决：仔细验证合并条件，编写单元测试覆盖各种边界情况。

调试技巧：

1. 对小规模测试用例手动计算预期结果
2. 打印中间结果验证各部分是否正确
3. 使用断言检查关键不变量
4. 对比暴力解法在小规模输入下的结果

# 调试示例：验证子集和生成是否正确 def test_subset_sum_generation(): nums = [1, 2, 3] # 暴力生成所有子集和 brute_force = set() for mask in range(1 << len(nums)): s = sum(nums[i] for i in range(len(nums)) if mask & (1 << i)) brute_force.add(s) # 折半搜索生成 left = nums[:len(nums)//2] right = nums[len(nums)//2:] left_sums = set() for mask in range(1 << len(left)): s = sum(left[i] for i in range(len(left)) if mask & (1 << i)) left_sums.add(s) right_sums = set() for mask in range(1 << len(right)): s = sum(right[i] for i in range(len(right)) if mask & (1 << i)) right_sums.add(s) # 验证组合是否覆盖所有可能性 combined = set() for l in left_sums: for r in right_sums: combined.add(l + r) assert brute_force == combined, "Subset sum generation incorrect" print("Test passed!")

7. 性能优化进阶

对于特别大的n（接近50），即使是折半搜索也可能面临性能挑战。这时可以考虑以下优化策略：

7.1 剪枝策略

在生成子集和的过程中，可以尽早排除不可能达到目标的情况。例如，如果当前累计和已经超过目标值，就可以停止进一步累加。

7.2 并行计算

由于左右两部分的计算是独立的，可以将其分配到不同的线程或进程中并行执行，最后合并结果。

7.3 近似算法

当精确解不是必须时，可以考虑使用随机采样或其他近似算法来获得接近最优的解。

7.4 位集优化

对于特定范围的子集和问题，可以使用位集来高效表示和计算可能的和值。

// C++示例：使用bitset高效计算子集和 const int MAX_SUM = 1000; bitset<MAX_SUM+1> dp; dp[0] = 1; // 初始状态：和为0可达 for (int num : nums) { dp |= dp << num; // 更新可达的和值 } // 现在dp[i]为1表示存在子集和为i

在实际项目中，我曾遇到一个需要处理n=45的子集和问题。通过结合折半搜索、剪枝和并行计算，我们将运行时间从预计的几小时缩短到了几分钟。关键是在生成左半部分子集和时，立即丢弃那些明显不可能与右半部分组合出有效解的部分，这减少了近70%的计算量。