algorithm - 统计总和大于或等于 k ​​的子集的个数

Question

给定一个包含 n 个元素的数组，需要计算总和大于或等于 k ​​的子集的数量。

例如 arr[] = {1,5,9,2,3}, k =16

1+5+9+2=17

1+5+9+3=18

1+5+9+2+3=20

5+9+2=16

5+9+3=17

5+9+2+3=19

答案是 6。

我所知道的一种方法是使用位掩码使用动态编程并检查 sum>=k 并递增计数。这种方法的问题是 N 应该非常小，因为位屏蔽涉及指数运行时间。

对于上述问题是否还有其他有效的算法。

提前致谢。

Answer 1

创建数组 Counts[Sum+1] 其中 Sum 是所有元素的总和
设置 Counts[0] = 1，其他元素 - 零
永远 x=arr[i] 从末尾扫描 Counts 数组并递增这些条目，这些条目可以由现有的到目前为止总和和 x

组成

if Counts[j - arr[i]] > 0 then  //this check might be omitted
   Counts[j] = Counts[j - arr[i]] +  Counts[j]

然后对 j>=k 的非零计数条目求和

复杂度为 O(Sum * N)

如果可能总和的范围很大但可能总和的数量不是那么多(如 arr=[1, 2, 3, 100000000, 100000001] 数组)，您可以利用内存方法和仅在 map 中存储真正存在的变体

示例:

arr=[1,2,3,5]
Counts = [1,0,0,0,0,0,0,0,0,0,0,0]
after arr[0]=1
Counts = [1,1,0,0,0,0,0,0,0,0,0,0]
after arr[1]=2
Counts = [1,1,1,1,0,0,0,0,0,0,0,0]
after arr[2]=3
Counts = [1,1,1,2,1,1,1,0,0,0,0,0]
after arr[3]=5
Counts = [1,1,1,2,1,2,2,1,2,1,1,1]

Counts[8] could be composed from 5 and existing Counts[3] with two variants
1+2+5; 3+5