Kotlin中如何检查列表任意N个元素组合的和是否≥指定值？

Great question! Let’s break this down into two practical scenarios: quickly verifying if such a combination exists, and generating all possible N-element combinations to check their sums (if you need more than just a yes/no answer).

Fast Check: Does Any Combination Exist? #

The most efficient way to answer this is to look at the largest N elements in the list. Their sum will be the maximum possible sum of any N elements—if this sum meets or exceeds your target, then yes, at least one valid combination exists. If even these top elements fall short, no other combination will work.

Here’s a clean Kotlin implementation:

fun hasAnyNElementsSumAtLeast(list: List<Int>, n: Int, target: Int): Boolean {
    require(n in 1..list.size) { "n must be between 1 and the list size" }
    
    // Sort descending, take top N elements, sum them
    val topNElementsSum = list.sortedDescending().take(n).sum()
    
    return topNElementsSum >= target
}

// Example usage
fun main() {
    val numbers = listOf(3, 1, 4, 1, 5, 9, 2, 6)
    println(hasAnyNElementsSumAtLeast(numbers, 3, 15)) // true (9+6+5=20 ≥15)
    println(hasAnyNElementsSumAtLeast(numbers, 2, 16)) // false (9+6=15 <16)
}

This runs in O(n log n) time (due to sorting), which is optimal for a yes/no check.

Generating All N-Element Combinations to Check Sums #

If you need to find every combination of N elements whose sum meets the target (not just confirm existence), you’ll need to generate all possible combinations. Important note: This is computationally expensive for large lists—binomial coefficients grow extremely fast (e.g., C(20,10) = 184,756 combinations).

Here’s a recursive function to generate combinations, paired with a filter for valid sums:

fun <T> combinations(list: List<T>, n: Int): List<List<T>> {
    if (n == 0) return listOf(emptyList())
    if (list.size < n) return emptyList()
    
    val first = list.first()
    val rest = list.drop(1)
    
    // Combinations including the first element
    val withFirst = combinations(rest, n-1).map { listOf(first) + it }
    // Combinations excluding the first element
    val withoutFirst = combinations(rest, n)
    
    return withFirst + withoutFirst
}

fun findAllNElementsSumAtLeast(list: List<Int>, n: Int, target: Int): List<List<Int>> {
    require(n in 1..list.size) { "n must be between 1 and the list size" }
    
    return combinations(list, n).filter { it.sum() >= target }
}

// Example usage
fun main() {
    val numbers = listOf(3, 1, 4, 1, 5)
    val validCombos = findAllNElementsSumAtLeast(numbers, 2, 7)
    println(validCombos) // [[3,4], [3,5], [4,5]]
}

Optimizations for Large Lists #

If working with big datasets, consider these tweaks:

• Early termination: Stop generating combinations as soon as you find one valid sum (if you only need existence, stick to the first method instead).
• Pruning: Sort the list first, then skip branches where even adding the remaining largest elements can’t reach the target.

Edge Cases to Handle #

• If n equals the list size: Only one combination exists (the entire list)—check its sum directly.
• If n is 1: Just verify if any element is >= the target (equivalent to checking the list’s maximum value).
• Negative numbers: The first method still works—taking the largest N elements (least negative or positive) gives the maximum possible sum.

内容的提问来源于stack exchange，提问作者Anga