求可重复使用指定数集元素得到目标值的所有组合算法

嘿，我完全懂你要解决的问题——你需要的是允许重复选取数集中元素的组合求和方案，而且要的是「无重复的组合」（比如4+4+8和8+4+4算同一个，不用重复输出）。这其实是经典的「无限背包组合问题」，和你之前找到的「元素不可重复」的场景核心差异在于每个元素可以被多次选取，同时要通过控制遍历顺序来避免重复组合。

核心思路 #

要实现这个需求，回溯（递归）是最直观且高效的方法，关键要做到两点：

• 允许重复选取：每次递归时，仍可以选择当前元素（而不是必须跳到下一个）
• 避免重复组合：只按数集的顺序往后选取元素（比如选了4之后，后续只能选4、5、6...不能回头选更小的元素），这样就不会生成顺序不同但元素相同的重复组合

代码实现（Python） #

这里给你一个可直接运行的示例，适配你给出的测试场景：

def find_reusable_combinations(nums, target):
    # 先排序数集（可选，但能让组合更有序，还能触发剪枝优化）
    sorted_nums = sorted(nums)
    result = []
    
    def backtrack(remaining_sum, current_path, start_index):
        # 找到有效组合：剩余和为0，保存当前路径
        if remaining_sum == 0:
            result.append(current_path.copy())
            return
        # 剩余和为负，这条路径无效，直接终止
        if remaining_sum < 0:
            return
        
        # 从start_index开始遍历，避免重复组合
        for i in range(start_index, len(sorted_nums)):
            current_num = sorted_nums[i]
            # 剪枝优化：如果当前元素已经大于剩余和，后面更大的元素肯定也不行，直接跳出循环
            if current_num > remaining_sum:
                break
            # 选取当前元素，加入路径
            current_path.append(current_num)
            # 递归：剩余和减去当前元素，start_index保持i（允许重复选当前元素）
            backtrack(remaining_sum - current_num, current_path, i)
            # 回溯：移除当前元素，尝试下一个可能的元素
            current_path.pop()
    
    backtrack(target, [], 0)
    return result

# 测试你的示例场景
number_set = [4, 5, 6, 7, 8]
target_sum = 16
combinations = find_reusable_combinations(number_set, target_sum)

# 打印结果
print("符合条件的组合：")
for combo in combinations:
    print("+".join(map(str, combo)))

代码说明 #

1. 排序与剪枝：先对数集排序，当遇到当前元素大于剩余目标值时，后面的元素更大，直接终止循环，减少不必要的递归，提升效率
2. start_index参数：这是避免重复组合的核心——每次递归从当前元素的索引开始，而不是从0，这样就不会出现「先选5再选4」的情况，确保组合的唯一性
3. 回溯过程：选取元素→递归探索→移除元素，逐步遍历所有可能的有效组合

运行结果 #

针对你给出的数集和目标值，运行后会输出：

4+4+4+4
4+4+8
4+5+7
4+6+6
5+5+6
8+8

完全覆盖你提到的期望组合，还补充了8+8这个符合条件的结果。

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