Swift中使用回溯算法实现砝码配重问题遇阻，求排查解决

Hey there! Let's break down why your current code only works for some inputs, then build a proper backtracking solution (plus a bonus optimized method since your weight set has a unique, pattern-based structure).

The Problem With Your Current Code #

Your snippet is doing a greedy linear scan—just adding weights in order if they're smaller than the target—instead of implementing backtracking's core "try, check, backtrack" logic. This fails because:

• You might overshoot the target by adding small weights first (e.g., trying to make 9 by adding 1+2+7 gives 10, which is too big, but the correct combo is 2+7)
• There's no way to "undo" a weight selection to try a different combination
• You're not recursively checking if the remaining target can be met with the remaining weights

Proper Backtracking Implementation #

Backtracking works by selecting a weight, recursively checking if the remaining target can be fulfilled with the remaining weights, and if not, undoing the selection (backtracking). We'll sort weights from largest to smallest first to reduce unnecessary recursive branches:

func findWeightCombination(target: Int, weights: [Int]) -> [Int]? {
    var result: [Int]?
    var currentCombo: [Int] = []
    // Sort weights descending to minimize recursive steps
    let sortedWeights = weights.sorted(by: >)
    
    func backtrack(remainingTarget: Int, startIndex: Int) {
        // Base case: we've hit the exact target
        guard remainingTarget != 0 else {
            result = currentCombo
            return
        }
        // Stop if we already found a valid combo
        guard result == nil else { return }
        
        // Iterate through weights starting from startIndex to avoid duplicate combos
        for i in startIndex..<sortedWeights.count {
            let weight = sortedWeights[i]
            // Skip weights larger than what we still need
            guard weight <= remainingTarget else { continue }
            
            // Try using this weight
            currentCombo.append(weight)
            // Recurse with the reduced target, starting from the next weight (no reusing)
            backtrack(remainingTarget: remainingTarget - weight, startIndex: i + 1)
            // Backtrack: remove the weight if it didn't lead to a solution
            currentCombo.removeLast()
        }
    }
    
    backtrack(remainingTarget: target, startIndex: 0)
    // Return sorted combo to match your example format
    return result?.sorted()
}

// Test it out!
let weights = [1,2,7,10,20,70,100,200,700]
print(findWeightCombination(target: 12, weights: weights) ?? []) // [2, 10]
print(findWeightCombination(target: 8, weights: weights) ?? []) // [1, 7]
print(findWeightCombination(target: 9, weights: weights) ?? []) // [2, 7]
print(findWeightCombination(target: 13, weights: weights) ?? []) // [1, 2, 10]

Bonus: Optimized Solution (No Backtracking Needed!) #

Your weight set follows a specific pattern: it's grouped by powers of 10 ([1,2,7], [10,20,70], [100,200,700], etc.). Each group can make any digit 1-3,7-9 with addition (digits 4-6 can't be made with addition, so we return nil for those). We can leverage this to skip backtracking entirely and solve the problem in linear time:

func findWeightCombinationFast(target: Int, weights: [Int]) -> [Int]? {
    var result: [Int] = []
    var remaining = target
    var divisor = 1
    
    while remaining > 0 {
        let digit = remaining % 10
        let baseWeights = [1*divisor, 2*divisor, 7*divisor]
        
        switch digit {
        case 1: result.append(baseWeights[0])
        case 2: result.append(baseWeights[1])
        case 3: result.append(contentsOf: [baseWeights[0], baseWeights[1]])
        case 7: result.append(baseWeights[2])
        case 8: result.append(contentsOf: [baseWeights[0], baseWeights[2]])
        case 9: result.append(contentsOf: [baseWeights[1], baseWeights[2]])
        default: // Digits 0,4,5,6 can't be made with addition
            return nil
        }
        
        remaining /= 10
        divisor *= 10
    }
    
    return result.sorted()
}

// Test the fast version
print(findWeightCombinationFast(target: 12, weights: weights) ?? []) // [2, 10]
print(findWeightCombinationFast(target: 8, weights: weights) ?? []) // [1, 7]

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