Python递归组合多整数数组无重叠置位元素的优雅实现方案

给定任意数量的正整数数组，查找所有符合要求的元素组合：

• 每个组合从每个数组中各选取一个元素
• 组合内任意两个元素的置位无重叠，即对组合内任意两个元素A、B，均满足A & B == 0

示例如下：

[[1, 2, 4], [8, 16]]   =>   [[1, 8], [1, 16], [2, 8], [2, 16], [4, 8], [4, 16]]
[[55, 49, 5, 61], [8, 97], [70, 20, 50]]   =>   [[49, 8, 70], [5, 8, 50]]
[[180, 44], [9, 182], [115, 110]]   =>   []

目前已有基础递归版本实现：

from itertools import chain
def find_combos(sets, combo=[], used_bits=0):
    set_idx = len(combo)
    if set_idx == len(sets):
        return [ combo ]
    to_try = filter(lambda n: not n & used_bits, sets[set_idx])
    # return [ c for n in to_try for c in find_combos(sets, combo+[n], used_bits|n) ]
    return list(chain.from_iterable(find_combos(sets, combo+[n], used_bits|n) for n in to_try))

当前实现存在频繁的列表解包与重封装操作，每一层递归都会生成新的临时列表，额外内存开销大，代码整洁度不足，需要更优雅、执行效率更高的实现，可借助itertools模块相关能力优化。

核心优化思路是减少中间列表的拷贝与拼接操作，通过惰性生成、路径复用、提前剪枝三个方向提升性能：

def find_combos(arrays):
    # 优先遍历长度更短的数组，更早剪枝无效路径
    sorted_arrays = sorted(arrays, key=len)
    def backtrack(idx, used_bits, path):
        if idx == len(sorted_arrays):
            yield path.copy()
            return
        for num in sorted_arrays[idx]:
            if not num & used_bits:
                path.append(num)
                yield from backtrack(idx + 1, used_bits | num, path)
                path.pop()
    return list(backtrack(0, 0, []))

优化点说明：

• 用生成器yield惰性返回合法组合，不需要每层递归构造临时列表再做chain拼接，省去大量列表解包、重封装开销
• 回溯过程复用同一个路径列表，通过append/pop维护当前选取状态，避免原实现中combo + [n]每次生成新列表的拷贝成本
• 前置排序剪枝：优先遍历元素更少的数组，能在递归浅层就过滤掉不合法的组合，大幅减少无效递归次数

如果需要基于itertools实现，也可以直接对笛卡尔积做合法性校验，但该方案没有提前剪枝，数据量大时性能远低于回溯版本：

from itertools import product

def find_combos_by_product(arrays):
    res = []
    for combo in product(*arrays):
        mask = 0
        valid = True
        for num in combo:
            if num & mask:
                valid = False
                break
            mask |= num
        if valid:
            res.append(list(combo))
    return res

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