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

Question

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
    }
    
}

Answer 1

This is a python equivalent of the soln you provided in the question.

paints = [2, 3, 0, 5]
mix_bucket_size = 5

ans = []


def get_combinations(active_bucket, paint_selection):
    if active_bucket == len(paints):
        if sum(paint_selection) == mix_bucket_size:
            ans.append(paint_selection)
        return

    total_paint_used_till_now = sum(paint_selection)
    space_left_in_mix_bucket = mix_bucket_size - total_paint_used_till_now

    for amount_of_paint_selected_from_active_bucket in range(min(space_left_in_mix_bucket, paints[active_bucket]) + 1):
        new_paint_selection = list(paint_selection)
        new_paint_selection[active_bucket] = amount_of_paint_selected_from_active_bucket
        get_combinations(active_bucket+1, new_paint_selection)


get_combinations(0, [0,0,0,0])


for a in ans:
    print(a)

The problem is that a lot of duplicate computations are being done.
You can read up about DP memoization and edit your existing code to add a memoization map.
I solved this problem following a Divide and Conquer approach to avoid redundant calculations.

def get_combinations(paints, mix_bucket_size):
    if len(paints) == 1:
        if paints[0] >= mix_bucket_size:
            return [[mix_bucket_size]]
        else:
            return []
    else:
        all_combinations = []

        paints_length = len(paints)
        lp = list(paints[:paints_length // 2])
        rp = list(paints[paints_length // 2:])

        for left_bucket_size in range(mix_bucket_size + 1):
            left_combinations = get_combinations(lp, left_bucket_size)
            right_combinations = get_combinations(rp, mix_bucket_size - left_bucket_size)

            for i in left_combinations:
                for j in right_combinations:
                    all_combinations.append(list(i) + list(j))

        return all_combinations

ans = get_combinations([2, 3, 0, 5], 5)
print(len(ans))

I also compared the performance of the two for different input sizes:-

[2, 3, 0, 5] 5
Total Solutions: 12
Original Approach   : 3.0040740966796875e-05 
D&C Approach        : 3.2901763916015625e-05 

[2, 3, 0, 5, 4] 8
Total Solutions: 49
Original Approach   : 0.00012493133544921875 
D&C Approach        : 0.00016188621520996094 

[2, 3, 0, 5, 2, 8, 3] 10
Total Solutions: 746
Original Approach   : 0.0016598701477050781 
D&C Approach        : 0.0006949901580810547 

[2, 3, 0, 5, 2, 8, 3, 3, 8] 12
Total Solutions: 13899
Original Approach   : 0.02570486068725586 
D&C Approach        : 0.00564885139465332 

[2, 3, 0, 5, 6, 0, 3, 7, 6, 4] 15
Total Solutions: 39220
Original Approach   : 0.10733675956726074 
D&C Approach        : 0.016217708587646484 

[2, 3, 0, 5, 6, 0, 3, 7, 6, 4, 7] 18
Total Solutions: 276347
Original Approach   : 0.7197868824005127 
D&C Approach        : 0.1888890266418457 

[2, 3, 0, 5, 8, 3, 5, 2, 9, 0, 7, 6, 4] 20
Total Solutions: 4507603
Original Approach   : 12.061448097229004 
D&C Approach        : 2.8866631984710693 

Hope this helps.