You need to enable JavaScript to run this app. 如何实现可处理含负元素数组的子集和动态规划算法
优惠活动
大模型
产品
解决方案
定价
更多

如何实现可处理含负元素数组的子集和动态规划算法

适配含负数值数组的子集和求解方案

原实现的核心缺陷

原来的非负版本算法存在两个无法适配负数输入的硬伤:

  • 动态表的列索引直接对应非负的和值,一旦数组包含负数,可凑出的子集和会覆盖负区间,直接用和值做列表下标会触发Python负索引的逻辑歧义,甚至代码里提前加的if n == 0 or inSum < 0: return判断,会直接把所有带负和的计算分支全部截断
  • 状态转移和回溯逻辑里的arr[i] <= j判断是针对非负元素设计的,遇到负元素时,这个判断会直接拦截合法的选择分支——比如元素值为-8时,只要目标和小于-8,即使存在合法的子集组合,也会被判断条件挡住

你之前尝试调整遍历边界为最小和到最大和的范围但没生效,本质是没有做负和值到合法列表下标的偏移映射:直接把j的遍历范围拉到负区间时,Python列表会把负的索引值解析为倒数位置的元素,完全不是你预期的和值对应的存储位置,自然算不出正确结果。

正确实现的核心逻辑

  • 提前遍历数组计算所有元素的取值边界:min_sum为所有负元素的累加值(即全选负元素能得到的最小和),max_sum为所有正元素的累加值(即全选正元素能得到的最大和),所有可能出现的子集和一定落在这个闭区间内
  • 设计固定偏移量offset = -min_sum,把所有可能出现的负和值全部映射为非负的合法列表下标:比如最小和为-8时,offset=8,和值-8对应下标0,和值0对应下标8,和值max_sum对应下标max_sum + offset,动态表的总列长为max_sum - min_sum + 1,完全覆盖所有可能的和值
  • 状态转移回归“选/不选当前元素”的核心规则,去掉非负场景下的大小判断:
    • 不选当前元素时,第i个位置能凑出的和s,继承第i-1个位置能凑出s的状态
    • 选当前元素时,第i个位置能凑出的和s,继承第i-1个位置能凑出s - arr[i]的状态
  • 回溯打印子集时,所有动态表的列索引都要加上offset做映射,去掉原逻辑里inSum >= arr[i]的无效判断。

修正后的可运行代码

def printPossibleSubsets(arr, i, inSum, pList, table, offset):
    # 处理第0个元素的边界回溯
    if i == 0:
        # 检查是否可以选第0个元素刚好凑出当前的inSum
        if inSum != 0 and table[0][inSum + offset]:
            pList.append(arr[i])
            print(pList)
            return
        # 不选任何元素刚好凑出0的场景
        if inSum == 0:
            print(pList)
            return
    
    # 分支1:不选当前i位置的元素,回溯上一层
    if table[i-1][inSum + offset]:
        bList = []
        bList.extend(pList)
        printPossibleSubsets(arr, i-1, inSum, bList, table, offset)
    
    # 分支2:选当前i位置的元素,回溯上一层(去掉原逻辑的inSum >= arr[i]判断)
    required_prev_sum = inSum - arr[i]
    if table[i-1][required_prev_sum + offset]:
        pList.append(arr[i])
        printPossibleSubsets(arr, i-1, required_prev_sum, pList, table, offset)     

def subsetSum(arr, n, inSum):
    # 提前计算所有可能的和值边界
    min_sum = sum([x for x in arr if x < 0])
    max_sum = sum([x for x in arr if x > 0])
    # 边界判断:目标和不在可能的范围内直接返回
    if inSum < min_sum or inSum > max_sum:
        print(f"There is no subset with {inSum}")
        return
    
    offset = -min_sum
    total_cols = max_sum - min_sum + 1
    # 初始化动态表
    table = [[False for _ in range(total_cols)] for _ in range(n)] 
    # 基础状态:选0个元素时,和为0
    table[0][0 + offset] = True
    # 选第0个元素的状态
    first_elem_sum = arr[0]
    if min_sum <= first_elem_sum <= max_sum:
        table[0][first_elem_sum + offset] = True
    
    # 填充动态表
    for i in range(1, n):
        curr_elem = arr[i]
        for j in range(total_cols):
            curr_sum = j - offset
            # 不选当前元素的状态
            table[i][j] = table[i-1][j]
            # 选当前元素的状态:计算上一步需要凑的和
            prev_sum = curr_sum - curr_elem
            if min_sum <= prev_sum <= max_sum:
                table[i][j] = table[i][j] or table[i-1][prev_sum + offset]

    # 检查是否存在匹配目标和的子集
    if not table[n-1][inSum + offset]:
        print(f"There is no subset with {inSum}")
        return

    pList = []
    printPossibleSubsets(arr, n-1, inSum, pList, table, offset)

if __name__ == "__main__":
    arr = [2, 3, -5, -8, 6, -1]
    inSum = 0
    subsetSum(arr, len(arr), inSum)

注意:这种带偏移的动态规划方案时间复杂度和空间复杂度依然是O(n*(max_sum - min_sum)),和非负版本的复杂度逻辑一致,只要和值范围不是极端大,就可以正常运行。

内容的提问来源于stack exchange,提问作者nevzatseferoglu

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.08 11:27:04