给定商品价格数组与固定金额，如何找出所有可购买的商品组合？

原思路的问题 #

两层嵌套循环只能枚举最多两个元素的组合，无法覆盖三个及以上元素的有效组合，自然达不到需求。

可行方案：回溯法 #

回溯法可以遍历所有可能的商品组合，通过剪枝优化效率，同时保留因原数组重复元素产生的重复组合（符合题目中“重复元素代表不同商品”的设定）。

实现步骤 #

• 定义递归函数，参数包含：当前处理的起始索引、已选商品列表、当前累加总价
• 递归终止条件：
  • 若当前累加总价等于目标金额，将已选列表加入结果集
  • 若当前累加总价超过目标金额，直接返回（剪枝，避免无效递归）
• 遍历从起始索引开始的每个元素：
  • 将当前元素加入已选列表，累加总价加上该元素价格
  • 递归调用函数，起始索引设为当前索引+1（确保每个商品仅被选择一次）
  • 回溯操作：将当前元素从已选列表移除，累加总价减去该元素价格

代码示例（Python） #

def find_combinations(prices, target):
    result = []
    def backtrack(start, path, current_sum):
        if current_sum == target:
            result.append(path.copy())
            return
        if current_sum > target:
            return
        for i in range(start, len(prices)):
            # 选择当前元素
            path.append(prices[i])
            # 递归处理下一个元素
            backtrack(i + 1, path, current_sum + prices[i])
            # 回溯，撤销选择
            path.pop()
    backtrack(0, [], 0)
    return result

# 测试示例
prices = [10, 15, 3, 4, 80, 110, 90, 92, 7, 5, 3, 7, 2]
amountOfMoney = 100
print(find_combinations(prices, amountOfMoney))

补充说明 #

• 该方法会枚举所有符合条件的组合，包括因原数组重复元素产生的重复结果（比如原数组有两个3，[90,5,3,2]会出现两次，对应不同的3商品）
• 若需要对结果去重（比如不考虑相同价格商品的不同实例），可以先对数组排序，在遍历过程中跳过与前一个元素相同的元素（前提是前一个元素已被处理过）

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