如何用列表元素生成指定数值的所有可能组合？

核心逻辑说明 #

我们要找的是不考虑元素顺序、可重复选取列表元素，使其总和等于目标数值的所有组合。比如目标4、列表[1,2]时，[1,1,2]和[1,2,1]算同一种，所以只保留前者，最终得到3种组合。

实现思路用递归回溯：

• 每次从列表中选一个元素，要求这个元素不小于上一次选的元素（避免重复组合）
• 用目标数值减去选中的元素，得到新的剩余目标
• 当剩余目标为0时，当前的组合就是有效解
• 当剩余目标小于0时，直接终止当前分支

Python 实现代码 #

def find_combinations(target, nums):
    # 先对列表排序，方便后续控制选取元素的顺序，避免重复组合
    nums = sorted(nums)
    result = []
    
    def backtrack(remaining, current_comb, start_index):
        # 剩余目标为0，找到有效组合
        if remaining == 0:
            result.append(current_comb.copy())
            return
        # 剩余目标小于0，这条路走不通，直接返回
        if remaining < 0:
            return
        
        # 从start_index开始遍历，保证只选大于等于上一个元素的数值
        for i in range(start_index, len(nums)):
            num = nums[i]
            # 加入当前元素到组合
            current_comb.append(num)
            # 递归调用，剩余目标减去当前元素，下次从当前索引开始（允许重复选当前元素）
            backtrack(remaining - num, current_comb, i)
            # 回溯：移除当前元素，尝试下一个元素
            current_comb.pop()
    
    backtrack(target, [], 0)
    return result

# 测试示例
if __name__ == "__main__":
    target_num = 4
    num_list = [1, 2]
    combinations = find_combinations(target_num, num_list)
    print(f"目标数值{target_num}，列表{num_list}的所有组合：")
    for idx, comb in enumerate(combinations, 1):
        print(f"{idx}. {comb}")

代码逐行解释 #

1. 排序处理：先对输入的nums排序，是为了后续通过start_index控制选取元素的顺序，确保组合不会重复。
2. 回溯函数backtrack：
   • remaining：当前还需要凑的数值
   • current_comb：当前正在构建的组合
   • start_index：遍历列表的起始索引，保证只选大于等于上一次选中的元素
3. 终止条件：
   • remaining == 0：把当前组合的副本加入结果列表（必须用copy()，否则后续修改会影响已存入的组合）
   • remaining < 0：当前元素太大，直接终止该分支
4. 遍历与回溯：
   • 从start_index开始遍历每个元素，加入当前组合
   • 递归调用backtrack，剩余目标减去当前元素，下次遍历仍从当前索引开始（允许重复选同一个元素）
   • 递归返回后，把当前元素从组合中移除（回溯），尝试下一个元素

运行结果 #

执行测试代码后，输出如下：

目标数值4，列表[1, 2]的所有组合：

1. [1, 1, 1, 1]
2. [1, 1, 2]
3. [2, 2]

完全符合示例结果。

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