Balance weights using backtracking algorithm in Swift

Question

I'm trying to implement a solution using the backtracking algorithm.

I have some weights [1,2,7,10,20,70,100,200,700...] and I want to return the weights after a given input/

For example input => 12 should return [2,10] For example input => 8 should return [1,7]

My code seem's not to work well. It works only for some input numbers like 13 or 8

for targetValue in [13] {
    var currentValue = 0
    var usedWeights: [Int] = []
    for weight in weights {
        if targetValue > weight {
            currentValue += weight
            usedWeights.append(weight)
        } else if weight > targetValue {
            let rememberLast = usedWeights.last ?? 0
            usedWeights.remove(at: usedWeights.count-1)
            currentValue -= rememberLast
            if currentValue > targetValue || currentValue < targetValue {
                let last = usedWeights.remove(at: usedWeights.count-1)
                currentValue -= last
                usedWeights.append(rememberLast)
                currentValue -= rememberLast
            print(usedWeights) /// [1, 2, 10] Yeah it work's :) but only for some number ..:(
            }
        }
    }
}

The used weights should be unique.

I have some trouble to find the weights.

This is how the algorithm work Input => 13
1
1+2
1+2+7
1+2+7+10 //currentValue is now 20
1+2+7 // still no solution get the last removed element and remove the current last element
1+2+10 // Correct weights

I hope you can help me and I explain what I'm doing wrong.

Answer 1

Here's one solution. Iterate in reverse through the weights. If the weight is less than or equal to the current total, use the weight.

let weights = [1,2,7,10,20,70,100,200,700] // the weights you have
let needed = 12 // The total weight you want

var total = needed // The current working total
var needs = [Int]() // The resulting weights needed
for weight in weights.reversed() {
    if weight <= total {
        needs.append(weight)
        total -= weight
    }
}
if total == 0 {
    print("Need \(needs) for \(needed)")
} else {
    print("No match for \(needed)")
}