如何实现可处理含负元素数组的子集和动态规划算法
适配含负数值数组的子集和求解方案
原实现的核心缺陷
原来的非负版本算法存在两个无法适配负数输入的硬伤:
- 动态表的列索引直接对应非负的和值,一旦数组包含负数,可凑出的子集和会覆盖负区间,直接用和值做列表下标会触发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
相关产品推荐
相关产品推荐

