如何用Python找出多数组取单元素和为指定值的所有组合

方法1：暴力枚举法（适合小规模数据） #

因为每个数组仅含5个元素，总共有 (5^5 = 3125) 种组合，直接枚举所有可能再筛选完全可行，代码简单直观：

import itertools

def find_combinations(arrays, target):
    # 生成所有跨数组的元素组合
    all_combinations = itertools.product(*arrays)
    # 筛选和等于目标值的组合
    return [comb for comb in all_combinations if sum(comb) == target]

# 示例用法
arrays = [
    [1, 2, 3, 4, 5],
    [6, 7, 8, 9, 10],
    [11, 12, 13, 14, 15],
    [16, 17, 18, 19, 20],
    [21, 22, 23, 24, 25]
]
target_sum = 50

result = find_combinations(arrays, target_sum)
for combo in result:
    print(combo)

方法2：分治法优化（适合数据规模扩展） #

如果后续数组元素数量或数组个数增加，暴力法效率会急剧下降。分治法通过拆分问题降低时间复杂度：将5个数组拆分为两组（比如前2个和后3个），先分别计算每组所有可能的和及对应的元素组合，再查找两组中和为目标值的互补对，合并得到最终组合。

from collections import defaultdict
import itertools

def find_combinations_divide_conquer(arrays, target):
    # 拆分数组为前后两部分
    mid = len(arrays) // 2
    left_arrays = arrays[:mid]
    right_arrays = arrays[mid:]

    # 计算左半部分所有可能的和及对应的组合
    left_sums = defaultdict(list)
    for combo in itertools.product(*left_arrays):
        s = sum(combo)
        left_sums[s].append(combo)

    # 计算右半部分所有可能的和，查找互补的左半组合并合并
    result = []
    for combo in itertools.product(*right_arrays):
        s = sum(combo)
        complement = target - s
        if complement in left_sums:
            for left_combo in left_sums[complement]:
                result.append(left_combo + combo)
    return result

# 示例用法（和上面的arrays、target_sum一致）
result = find_combinations_divide_conquer(arrays, target_sum)
for combo in result:
    print(combo)

说明 #

• 暴力法利用itertools.product生成笛卡尔积，代码简洁，对于5×5的场景完全够用。
• 分治法通过空间换时间，将时间复杂度从 (O(n^k))（k为数组数量）降低到 (O(n^{k/2} + n^{k - k/2}))，当数组数量或元素较多时优势明显。

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