python列表组合高效率方法？

Question

a = [i for i in range(1, 8000)]

假如有个这样的列表， 我需要把里面的所有值组合 然后求 组合的总和与100差的最小值。

例如 1和2组合 1+2 =3 与100 差 3-100 == -97 ， 1和3组合 1+3-100 = -96 ， 1和4组合，1+4-100=-95..... 1+99-100=0 ....依次类推， 1+2+3+4+5+6...+7999-100=?

则最小值依次为97， 96,95...0 然后找出最小的值就是0. 并且把符合 最小值等于0的组合 都放到一个列表中。

最终得到 a1= [[1,99],[2,98],......[1,2,97],....[1,2,3,94].........]

有没有高效的计算方法？

正常的计算方法 效率都比较低效率。

Answer 1

def find_combinations(target_sum, numbers):
    i, j = 0, len(numbers) - 1
    combinations = []

    while i < j:
        if numbers[i] + numbers[j] == target_sum:
            combinations.append([numbers[i], numbers[j]])
            i += 1
            j -= 1
        elif numbers[i] + numbers[j] < target_sum:
            i += 1
        else:
            j -= 1

    return combinations

a = [i for i in range(1, 8000)]
target_sum = 100
combinations = find_combinations(target_sum, a)

前10个组合

[[1, 99],
 [2, 98],
 [3, 97],
 [4, 96],
 [5, 95],
 [6, 94],
 [7, 93],
 [8, 92],
 [9, 91],
 [10, 90]]

Answer 2

可以用动态规划

def find_min_difference(a, target):
    n = len(a)
    dp = [float('inf')] * (target + 1)
    dp[0] = 0

    for num in a:
        for t in range(target, num - 1, -1):
            dp[t] = min(dp[t], dp[t - num] + num)

    min_diff = dp[target]
    result = []

    def find_combinations(curr_comb, idx, remaining_diff):
        nonlocal min_diff, result
        if remaining_diff == 0:
            if len(curr_comb) > 1:
                result.append(curr_comb[:])
            return
        if idx == n:
            return
        if dp[remaining_diff] == dp[remaining_diff - a[idx]] + a[idx]:
            find_combinations(curr_comb + [a[idx]], idx + 1, remaining_diff - a[idx])
        find_combinations(curr_comb, idx + 1, remaining_diff)

    find_combinations([], 0, min_diff)

    return result

a = [i for i in range(1, 8000)]
target = 100
result = find_min_difference(a, target)
print(result)