统计和大于等于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，其他元素-零

For ever x=arr[i] scan Counts数组从末尾开始并递增这些条目，这些条目可以由目前为止的sums和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]数组)，您可以利用记忆化方法，只在映射中存储真正存在的变体

示例：

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

Answer 2

一种方法是使用递归创建子集，并在原始集合中省略的元素的总和大于total-k时停止递归，其中total是数组中所有元素的总和。

下面是一些说明该方法的Java代码：

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class SubSet
{

    public static void main(String[] args)
    {
        Integer[] set = { 1, 5, 9, 2, 3 };
        List<List<Integer>> subsets = subsetsK(set, 16);
        for (List<Integer> subset : subsets)
        {
            System.out.println(subset);
        }
    }

    static List<List<Integer>> subsetsK(Integer[] arr, int k)
    {
        int t = 0;
        for (int n : arr) t += n;

        List<List<Integer>> subsets = new ArrayList<>();
        allSubsets(subsets, arr, new BitSet(arr.length), 0, 0, t - k);
        return subsets;
    }

    public static void allSubsets(List<List<Integer>> subsets, Integer[] arr, BitSet off, int pos, int sum, int lim)
    {
        if(sum > lim) return;

        if(pos == arr.length)
        {
            subsets.add(toSubset(arr, off));
            return;
        }

        off.set(pos);
        allSubsets(subsets, arr, off, pos + 1, sum + arr[pos], lim);

        off.clear(pos);
        allSubsets(subsets, arr, off, pos + 1, sum, lim);
    }

    static List<Integer> toSubset(Integer[] arr, BitSet off)
    {
        List<Integer> ss = new ArrayList<>();
        for (int i = 0; i < arr.length; i++)
        {
            if (!off.get(i))
                ss.add(arr[i]);
        }
        return ss;
    }   
}

输出：

[5, 9, 3]
[5, 9, 2]
[5, 9, 2, 3]
[1, 5, 9, 3]
[1, 5, 9, 2]
[1, 5, 9, 2, 3]

您可以在此处运行/编辑代码：Ideone