2023-05-25

Find all numbers in a set of maxima that sum to a given number

I am struggling to think of an algorithm which matches my needs. I have a list of integers in a set, each integer represents a maximum value, the list can contain >= 1 entries. I would like to find all the combinations of integers within these maxima that sum to a given value.

For example for a list of 4 maxima = [2, 3, 0, 5] and given value = 5, solutions are:

[2, 3, 0, 0]
[2, 2, 0, 1]
[2, 1, 0, 2]
[2, 0, 0, 3]
[1, 3, 0, 1]
[1, 2, 0, 2]
[1, 1, 0, 3]
[1, 0, 0, 4]
[0, 3, 0, 2]
[0, 2, 0, 3]
[0, 1, 0, 4]
[0, 0, 0, 5]

I have found some great algorithms related to this but they only address the combinations of the integers in the list which sum to the given value (i.e. in above example, would generate [2, 3] and [5] but not all the other combinations that I am interested in.

I have built a solution (in Swift) that solves this with blunt force (see below), but I am looking for something far more efficient.

import UIKit

let avail = [2, 3, 0, 5]
let sol = [0, 0, 0, 0]
var solList = [[Int]]()
let target = 5
let inc = 1
var calls = 0

generate(soln: sol, idx: 0)

print("calls : \(calls) solutions \(solList.count)")
for entry in solList {
    print(entry)
}

func generate(soln: [Int], idx: Int) -> Void {
    calls += 1
    
    let solnTotal = soln.reduce(0, +)
    
    if solnTotal > target {return}
    
    if solnTotal == target {
        solList.append(soln)
        //print(soln)
        return
    }
    
    if idx == soln.count {return}
    
    var tmp = soln[idx]
    while tmp <= avail[idx] {
        var solNext = soln
        solNext[idx] = tmp
        let solnTotal = solNext.reduce(0, +)
        if solnTotal > target {break}
        generate(soln: solNext, idx: idx + 1)
        tmp += inc
    }
    
}


No comments:

Post a Comment