hooliooo
06/29/2020, 2:56 PM/**
* 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.ktMichael de Kaste
06/29/2020, 4:24 PMhooliooo
06/29/2020, 4:44 PMLeoColman
06/29/2020, 4:56 PMMichael de Kaste
06/29/2020, 6:16 PMhooliooo
06/29/2020, 6:45 PMAndrew
06/30/2020, 5:07 AMhooliooo
06/30/2020, 6:25 AM