数组中不大于k的最大子集和：现有解法内存溢出求最优方案

给定整数数组和整数k，需找出数组中不大于k的最大可能子集和。

• 示例：数组=[7,6,9,11]，k=25，答案为24（子集6+7+11的和）
• 约束：数组长度1-40，k及数组元素值为1到10^9

使用以下两段Stack Overflow代码处理大输入时，均触发Memory Error：
第一段代码在cur = [False] * (len(items) + 1)行报错：

def largest_subset(items, k):
    res = 0

    # We can form subset with value 0 from empty set,
    # items[0], items[0...1], items[0...2]
    arr = [[True] * (len(items) + 1)]

    for i in range(1, k + 1):
        # Subset with value i can't be formed from empty set
        cur = [False] * (len(items) + 1)

        for j, val in enumerate(items, 1):
            # cur[j] is True if we can form a set with value of i from
            # items[0...j-1]
            # There are two possibilities
            # - Set can be formed already without even considering item[j-1]
            # - There is a subset with value i - val formed from items[0...j-2]
            cur[j] = cur[j-1] or ((i >= val) and arr[i-val][j-1])
        if cur[-1]:
            # If subset with value of i can be formed store
            # it as current result
            res = i

        arr.append(cur)
    return res

第二段代码在subsets = [s + (val,) for s in prev_subsets]行报错：

def subset_sum(vals, target=0):
    sums = {0: [()]}  # key=sum, value=list of subsets for the sum
    if target in sums:
        yield from sums[target]  # annoying base case
    for val in vals:
        items = sums.items()  # don't change dict size during iteration
        sums = dict(items)
        for prev_sum, prev_subsets in items:
            sum_ = prev_sum + val
            subsets = [s + (val,) for s in prev_subsets]
            sums[sum_] = sums.get(sum_, []) + subsets
            if sum_ <= target:
                yield from subsets

核心思路：折半枚举（Meet-in-the-Middle） #

数组长度最多40，直接枚举所有子集（2^{40≈1e12）不现实，但分成两组各20个元素，每组子集和数量仅为2}20≈1e6，完全可以存储和处理。具体步骤：

1. 将数组分成左右两部分（比如前n//2个元素和剩余元素）
2. 分别生成两部分的所有可能子集和，存入两个列表
3. 对其中一个列表排序，方便后续二分查找
4. 遍历另一列表中的每个和s，在排序后的列表中找最大的t，使得s + t ≤ k，记录所有符合条件的s+t中的最大值

代码实现 #

def max_subset_sum_less_or_equal_k(arr, k):
    n = len(arr)
    # 分成左右两部分
    left = arr[:n//2]
    right = arr[n//2:]
    
    # 生成左半部分所有子集和
    left_sums = []
    def generate_sums(nums, idx, current_sum, sums):
        if idx == len(nums):
            sums.append(current_sum)
            return
        # 选当前元素
        generate_sums(nums, idx+1, current_sum + nums[idx], sums)
        # 不选当前元素
        generate_sums(nums, idx+1, current_sum, sums)
    
    generate_sums(left, 0, 0, left_sums)
    generate_sums(right, 0, 0, right_sums)
    
    # 排序右半部分的和，用于二分查找
    right_sums.sort()
    max_sum = 0
    
    for s in left_sums:
        if s > k:
            continue
        # 找最大的t，使得s + t <=k
        target = k - s
        # 二分查找右半部分中<=target的最大值
        low, high = 0, len(right_sums)-1
        best_t = 0
        while low <= high:
            mid = (low + high) //2
            if right_sums[mid] <= target:
                best_t = right_sums[mid]
                low = mid +1
            else:
                high = mid -1
        current_total = s + best_t
        if current_total > max_sum:
            max_sum = current_total
        # 提前终止：如果已经等于k，直接返回
        if max_sum == k:
            return k
    return max_sum

# 测试示例
print(max_subset_sum_less_or_equal_k([7,6,9,11],25)) # 输出24

为什么原方法失效？ #

• 第一段代码是二维动态规划，当k达到1e9时，需要创建长度为1e9+1的数组，每个元素是长度41的布尔列表，内存占用直接超出限制。
• 第二段代码存储所有子集的具体组合，40个元素的子集数量是2^40≈1e12，根本无法存储，必然触发内存错误。

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