如何用Python找出无重复元素且和≥指定值的组合？

你现在的代码只是枚举了所有两两组合中满足和≥K的情况，但这些组合会重复使用元素。你实际需要的是把所有元素划分成若干不重叠的分组，每个分组的和≥K，分组可以是单个元素（当元素本身≥K时）或多个元素的组合。

解决方案：回溯法找合法划分 #

以下代码通过回溯算法，尝试找出一种符合要求的元素划分方式，保证所有元素不重复使用，且每个分组的和≥K：

from itertools import combinations

def find_valid_partitions(lst, K):
    # 从大到小排序，优先处理大元素，减少回溯分支
    sorted_lst = sorted(lst, reverse=True)
    element_used = [False] * len(sorted_lst)
    partitions = []

    def backtrack(start_idx):
        # 所有元素都已分配，返回成功
        if all(element_used):
            return True
        # 跳过已经被使用的元素
        while start_idx < len(sorted_lst) and element_used[start_idx]:
            start_idx += 1
        if start_idx >= len(sorted_lst):
            return True

        # 尝试从当前位置开始，所有可能长度的子集
        for subset_length in range(1, len(sorted_lst) - start_idx + 1):
            # 生成当前位置开始的所有长度为subset_length的组合
            for idx_combo in combinations(range(start_idx, len(sorted_lst)), subset_length):
                # 检查组合内元素是否都未被使用
                if all(not element_used[idx] for idx in idx_combo):
                    subset_sum = sum(sorted_lst[idx] for idx in idx_combo)
                    if subset_sum >= K:
                        # 标记元素为已使用
                        for idx in idx_combo:
                            element_used[idx] = True
                        partitions.append(tuple(sorted_lst[idx] for idx in idx_combo))
                        # 递归处理剩余元素
                        if backtrack(start_idx + 1):
                            return True
                        # 回溯，撤销选择
                        partitions.pop()
                        for idx in idx_combo:
                            element_used[idx] = False
        return False

    backtrack(0)
    return partitions

# 测试代码
input_list = [10, 20, 30, 40, 50, 90, 100, 101]
target_sum = 100
result = find_valid_partitions(input_list, target_sum)
print(result)

示例输出 #

运行后会得到类似这样的合法划分：

[(101,), (100,), (90, 20), (50, 40, 30, 10)]

这个结果里每个分组的和都≥100，且所有元素只使用了一次，符合你的要求。

补充说明 #

• 回溯法会尝试所有可能的组合，找到一种可行的划分即可返回，如果你需要所有可能的划分，可以去掉return True的逻辑，收集所有符合条件的结果。
• 先对列表从大到小排序，能有效减少回溯的分支数量，提升效率。

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