Scala最小子集和问题：现有解法存疑，探讨更优实现方案

给定N个正整数组成的列表，任务是找出和大于等于指定值S的最小子集的大小。示例输入列表为[4, 8, 10, 12]，针对S值4、13、30、100，预期输出分别为1、2、3、-1（当列表总和小于S时）。

本人已实现如下Scala尾递归解法：

def subsetsSum(set: List[Int], targetValue: Int): Int = {
  @tailrec
  def subsetsSumHelp(upperLevelSet: List[Int]): Int = {
    val sum = upperLevelSet.sum
    if (sum > targetValue) subsetsSumHelp(upperLevelSet.tail) else upperLevelSet.size
  }

  val initialSum = set.sum
  if (initialSum < targetValue) -1 else subsetsSumHelp(set.tail)
}

val testCase = 13
val input = List(4, 8, 10, 12)

println(subsetsSum(input.sorted(Ordering.Int.reverse), testCase))

该方案需预先对列表进行降序排序，想了解是否存在更优的实现方案，例如基于二分查找的思路？

首先，你的核心思路是正确的——优先选取最大元素是寻找最小子集的最优贪心策略，因为要使用最少的元素凑出≥S的和，优先取最大的正整数必然是最高效的，这个逻辑在正整数集合中完全成立。

现有解法的效率问题 #

你当前的实现存在明显的性能瓶颈：每次递归调用upperLevelSet.sum都会遍历整个子列表求和，时间复杂度为O(n)，导致整体时间复杂度达到O(n²)，当列表元素较多时效率会很低。

基于前缀和+二分查找的优化方案 #

通过预处理前缀和数组，再结合二分查找，可以将整体时间复杂度优化到O(nlogn)，具体步骤如下：

1. 对列表进行降序排序，保证贪心策略的执行基础；
2. 计算前缀和数组：前缀和数组的第i位表示前i个最大元素的累加和（例如排序后的[12,10,8,4]，前缀和数组为[12,22,30,34]）；
3. 查找前缀和数组中第一个≥S的元素，其对应的索引+1就是最小子集的大小；若整个前缀和数组的总和仍小于S，返回-1；
4. 利用二分查找可以将查找步骤的时间复杂度从O(n)降到O(logn)，进一步提升效率。

Scala优化实现示例 #

def minSubsetSize(nums: List[Int], s: Int): Int = {
  val sortedNums = nums.sorted(Ordering.Int.reverse)
  // 生成前缀和数组，scanLeft初始值0会生成第一个元素0，用tail跳过
  val prefixSums = sortedNums.scanLeft(0)(_ + _).tail
  val totalSum = prefixSums.lastOption.getOrElse(0)
  
  if (totalSum < s) -1
  else {
    // 查找第一个≥s的前缀和的索引，索引+1即为子集大小
    prefixSums.indexWhere(_ >= s) + 1
  }
}

// 测试用例验证
val input = List(4, 8, 10, 12)
println(minSubsetSize(input, 4))   // 输出1
println(minSubsetSize(input, 13))  // 输出2
println(minSubsetSize(input, 30))  // 输出3
println(minSubsetSize(input, 100)) // 输出-1

方案优势说明 #

• 贪心策略的正确性：正整数场景下，优先选最大元素能最快凑够目标和，不存在反例；
• 时间复杂度优化：排序的时间复杂度为O(nlogn)，前缀和计算为O(n)，查找步骤为O(logn)，整体复杂度为O(nlogn)，远优于原实现的O(n²)；
• 无更优替代方案：这类问题的时间复杂度下限就是O(nlogn)，因为必须通过排序来保证贪心逻辑的有效性，不存在无需排序的更优解法。

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