如何修改Python函数实现筛选总和介于0.4和0.7之间的所有子数组

问题根因 #

你修改后的判断直接把总和≥0.7的数组的递归分支完全剪掉了，导致这类数组内部符合「总和在0.4~0.7之间」的子数组也不会被遍历到，自然得不到预期结果。
原逻辑的剪枝只针对「总和≤下界」的数组是合理的：因为你的数组元素全为正数，当前数组总和都小于等于0.4的话，它的所有子数组（元素更少）总和只会更小，不可能符合要求，可以直接剪掉分支。但总和≥0.7的数组只是自身不符合要求，删除元素后的子数组完全可能落在目标区间内，不能直接剪枝，只是不需要把它本身加入结果集即可。

正确修改方案 #

我们调整返回逻辑即可：只把总和落在目标区间的数组加入结果集，总和超过上界的数组仍然继续递归遍历子数组，仅剪总和≤下界的分支。为了代码更灵活，我们可以把上界也做成参数：

def find_subarr(arr: tuple, lower_bound, upper_bound):
    arr = tuple(arr)
    current_sum = sum(arr)
    # 仅剪总和小于等于下界的分支：元素全正，子数组总和只会更小，不可能符合要求
    if current_sum <= lower_bound:
        return set()

    ret = set()
    # 只有总和落在目标区间的当前数组才加入结果
    if current_sum < upper_bound:
        ret.add(arr)
    
    # 无论当前数组总和是否超过上界，都继续递归遍历子数组
    for i in range(len(arr)):
        tmp_arr = list(arr)
        del tmp_arr[i]
        tmp_arr = tuple(tmp_arr)
        ret |= find_subarr(tmp_arr, lower_bound, upper_bound)

    return ret

subarrays = find_subarr([0.1,0.2,0.3,0.4,0.5], 0.4, 0.7)
for subarr in sorted(subarrays, key=lambda l: (len(l), sum(l))):
    print(subarr)

运行后将输出所有符合要求的子数组：

(0.5,)
(0.1, 0.4)
(0.2, 0.3)
(0.1, 0.5)
(0.2, 0.4)
(0.1, 0.2, 0.3)

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