基于回溯法的最优权重子集和问题修复：求最少权重组合

你的代码本质上是贪心算法的变形，并非真正的回溯法——这就是它返回非最优解的核心原因。贪心算法在这类“找最少数量权重组合”的问题中，只有当权重集合满足「贪心选择性质」（比如每个权重是前一个的整数倍，且能保证局部最优导出全局最优）时才有效，但你的案例里，贪心选两个700后剩下的107只能用多个小权重凑，最终得到10个元素的组合；而最优解是用一个700加四个200加一个7，仅6个元素，贪心在这里失效了。

另外你的代码还有几个关键问题：

• 递归逻辑只是简单移除最后一个权重再重试贪心，没有实现回溯法的核心：尝试选/不选当前权重，递归探索所有可能路径，并回溯恢复状态。
• 直接修改原数组的引用（weights.removeLast()），会破坏后续递归分支的权重集合，且没有回溯恢复操作。
• 没有跟踪当前找到的最优解（最少元素数的组合），只是返回第一个凑成目标的组合。

回溯法修复实现 #

下面是符合要求的Swift回溯法实现，针对可重复使用权重（无限背包）的最少数量组合问题：

func findMinWeightCombination(target: Int, weights: [Int]) -> [Int] {
    // 先降序排序，优先尝试大权重，更快找到短组合，方便剪枝
    let sortedWeights = weights.sorted(by: >)
    var bestCombination: [Int] = []
    
    // 回溯函数：currentPath是当前已选权重，remaining是剩余目标值，startIndex是当前遍历的权重索引（避免重复组合）
    func backtrack(currentPath: [Int], remaining: Int, startIndex: Int) {
        // 剪枝：如果当前路径长度已经等于或超过最优解长度，没必要继续
        if !bestCombination.isEmpty && currentPath.count >= bestCombination.count {
            return
        }
        
        // 找到一个有效组合
        if remaining == 0 {
            // 如果当前组合更短，更新最优解
            if bestCombination.isEmpty || currentPath.count < bestCombination.count {
                bestCombination = currentPath
            }
            return
        }
        
        // 遍历权重，从startIndex开始避免重复（比如选200之后还能再选200，但不用回头选700）
        for i in startIndex..<sortedWeights.count {
            let weight = sortedWeights[i]
            // 如果当前权重超过剩余值，跳过（因为降序，后面的更小，也可以直接break）
            guard weight <= remaining else {
                continue
            }
            
            // 选择当前权重，递归
            backtrack(currentPath: currentPath + [weight], remaining: remaining - weight, startIndex: i)
            // 回溯：这里不需要手动移除，因为currentPath是值传递，递归返回后自动恢复到之前的状态
        }
    }
    
    backtrack(currentPath: [], remaining: target, startIndex: 0)
    return bestCombination
}

// 测试
let target = 1507
let weights = [2,7,20,70,200,700]
print(findMinWeightCombination(target: target, weights: weights))
// 输出：[700, 200, 200, 200, 200, 7]

关键说明 #

1. 降序排序与剪枝：先把权重从大到小排序，这样能优先尝试大权重，更快找到元素更少的组合；一旦当前路径长度已经不短于已找到的最优解，直接剪枝停止递归，提升效率。
2. 回溯逻辑：对于每个权重，我们尝试选中它（因为可以重复使用，所以递归时startIndex保持当前索引，允许再次选同一个权重），递归探索剩余目标；递归返回后，由于currentPath是值传递，自动恢复到选之前的状态，无需手动回溯移除元素。
3. 最优解跟踪：用bestCombination变量保存当前找到的最短组合，每次找到有效组合时，只有当它更短才更新最优解。

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