Hi guys, I’m currently working on a microservice ...

# announcements

[hooliooo]

Hi guys,

I’m currently working on a microservice where I must use a combinatorial algorithm for my application, I’m using an algorithm that tackles the combination sum II programming problem:

Here is my implementation (copied from the internet):

/**
     * Given a collection of integers and a target integer (target),
     * find all unique combinations of integers where the sums of the combinations equal the target.
     * @param integers The integers used in the combinations
     * @param target The target sum
     * @return List<List<Int>> which represents all the possible combinations of integers that sum up to the target
     */
    private fun combinationSumII(integers: IntArray, target: Int, limit: Int): List<List<Int>> {
        fun backtrack(
            integers: IntArray,
            target: Int,
            limit: Int,
            index: Int,
            trace: List<Int>,
            allCombinations: MutableList<List<Int>>
        ) {
            for (i in index until integers.size) {
                val current = integers[i]
                if (i > index && current == integers[i - 1]) continue
                if (trace.size >= limit) break

                val remainingValue = target - current
                when {
                    (remainingValue == 0) -> {
                        val set = ArrayList<Int>(trace)
                        set.add(current)
                        allCombinations.add(set)
                    }
                    (remainingValue > 0) -> {
                        val newTrace = ArrayList<Int>(trace)
                        newTrace.add(current)
                        backtrack(integers, remainingValue, limit, i + 1, newTrace, allCombinations)
                    }
                }
            }
        }

        val allCombinations = mutableListOf<List<Int>>()
        val result = mutableListOf<Int>()
        integers.sort()
        backtrack(
            integers = integers,
            target = target,
            limit = limit,
            index = 0,
            trace = result,
            allCombinations = allCombinations
        )
        return allCombinations
    }

For small sets of data this will suffice but there are edge cases integers is a big array, and target is a bigger int.

Is there anyway to make this more efficient? I need this algorithm to be as fast as possible.

Test data with long computation time:
Scenario 1

val integers = 43..166.toList().toIntArray()
val target = 600
val limit = 5

Scenario 2

val integers = (22..166).toList().toIntArray()
val target = 554
val limit = 5

References:
Problem: https://leetcode.com/problems/combination-sum-ii/
Algorithm: https://github.com/topwu/leetkotlin/blob/master/src/main/kotlin/leetcode/CombinationSumII.kt

[Michael de Kaste]

well the thing is; there is in insane amount of possibilities once your list starts getting very large, so it's very obvious the problem explodes with your input.

I do have a couple of questions: Are duplicates still allowed? Do you really want ALL the possible solutions or is a subset enough?

[hooliooo]

Duplicates are only allowed if they are in the IntArray. Otherwise no.

Unfortunately I think I do need all the possible solutions because the output from this algorithm is filtered further based on other constraints

[LeoColman]

Perhaps you can return a sequence of List<Int> instead of a list?

[LeoColman]

This way you could calculate the values on demand, and not all at once

[Michael de Kaste]

I think the algorithm is pretty refined, I tried making one with a treeset, but the results were roughly the same. The cool thing about making a recursive sequence however is that you can run it in parallel using coroutines.

Another thing is, you pointed out you wanted to filter the output further, but that can still be done within the scope of using a sequence. But if you truly want ALL the outputs following that, then you really have to run all the steps.

[hooliooo]

Did you manage to implement this with parallel coroutines? That might be the way to go to speed up the processing 🤔

[Andrew]

Did you check the fastest runtimes in LC? I tried the one in the link you gave and there are faster results which you can view the code for, LC speed test is limited so seeing how it scales with larger examples might be better. Also uses recursion so maybe a chance to optimize with coroutines as well.

[hooliooo]

I managed to filter out numbers from the IntArray that aren’t viable for my constraints, and it sped up the algorithm drastically. Thanks for the input