数字列表按指定和分组：回溯法低效，求高效解决方案

给定一组目标和（比如[7,6]）和一组数字（比如[4,3,2,2,2]），两类列表元素顺序随机，需要返回形如[[4,3],[2,2,2]]的分组结果——每个分组的和对应一个目标和，所有数字都要被分配。当前用回溯解法在列表变长后耗时极长，求高效解决思路。

原回溯实现代码 #

def find_best_partition(numbers, targets):
    best_partitions = []
    best_difference = float('inf')

    def partition_helper(numbers, targets, current_partitions, current_sums, current_index):
        nonlocal best_partitions, best_difference

        if current_index == len(numbers):
            difference = sum(numbers) - sum(current_sums)
            if difference < best_difference and set(current_sums).issubset(set(targets)):
                best_difference = difference
                best_partitions = [partition[:] for partition in current_partitions]
            return

        for i, target in enumerate(targets):
            if current_sums[i] + numbers[current_index] <= target:
                current_partitions[i].append(numbers[current_index])
                current_sums[i] += numbers[current_index]
                partition_helper(numbers, targets, current_partitions, current_sums, current_index + 1)
                current_partitions[i].pop()
                current_sums[i] -= numbers[current_index]

    initial_partitions = [[] for _ in range(len(targets))]
    initial_sums = [0] * len(targets)

    partition_helper(numbers, targets, initial_partitions, initial_sums, 0)
    return best_partitions

高效优化思路 #

1. 核心剪枝与预处理 #

• 排序优化：将数字和目标和都按降序排序，优先分配大数字。大数字的匹配约束更强，能快速排除无效分支，大幅减少回溯次数。
• 去重剪枝：若当前数字与前一个数字相同，且前一个数字在同一分组的尝试已失败，直接跳过当前数字的相同分组尝试，避免重复计算。
• 状态剪枝：如果某个分组的当前和已等于目标和，后续数字不再往该分组添加；若当前数字加入分组后超过目标和，直接跳过该分组。
• 可行性预判：先计算数字总和与目标和总和，若不相等，直接返回空（若允许部分匹配可跳过此步，但完全匹配场景下这步能提前终止无效计算）。

2. 约束逻辑修正 #

原代码用set(current_sums).issubset(set(targets))判断匹配，会出现多个分组匹配同一目标的错误情况（比如目标是[7,6]，两个分组和都是7也会被判定为有效）。应改为每个分组的最终和必须恰好对应一个未被占用的目标，可通过排序后一一匹配目标，或用已匹配标记跟踪目标使用情况。

3. 算法升级：分支定界+回溯 #

在回溯过程中，一旦找到完全匹配的解，直接终止所有后续分支（因为完全匹配是最优解）；若当前分支的剩余数字无法填补目标和的缺口，也直接剪枝。

优化后的代码示例（核心剪枝版） #

def find_best_partition(numbers, targets):
    # 先验证完全匹配可行性
    if sum(numbers) != sum(targets):
        return []
    
    # 降序排序，优先处理大数字
    numbers.sort(reverse=True)
    targets.sort(reverse=True)
    target_count = len(targets)
    best_result = None

    def backtrack(num_index, partitions, current_sums):
        nonlocal best_result
        if best_result is not None:
            return  # 已找到最优解，直接终止
        
        if num_index == len(numbers):
            # 排序后分组和需与目标和完全一致
            if current_sums == targets:
                best_result = [p.copy() for p in partitions]
            return
        
        current_num = numbers[num_index]
        for i in range(target_count):
            # 剪枝：分组已达目标，跳过
            if current_sums[i] == targets[i]:
                continue
            # 剪枝：加入当前数字后超过目标，跳过
            if current_sums[i] + current_num > targets[i]:
                continue
            # 剪枝：去重，避免重复尝试相同状态
            if i > 0 and current_sums[i] == current_sums[i-1] and current_num == numbers[num_index-1]:
                continue
            
            partitions[i].append(current_num)
            current_sums[i] += current_num
            backtrack(num_index + 1, partitions, current_sums)
            partitions[i].pop()
            current_sums[i] -= current_num
            
            # 剪枝：空分组尝试失败后，无需尝试其他空分组
            if current_sums[i] == 0:
                break

    backtrack(0, [[] for _ in range(target_count)], [0]*target_count)
    return best_result if best_result is not None else []

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