《集合计数》题目分析

本题是一道枚举题目。

首先我们可以对数组排序，不妨设A1, A2, ... AN是经过从小到大排序后的数组。

之后我们可以枚举集合中的最小值，不妨设是Ai。

然后我们找到满足Ai+Aj <= K的最大的Aj。注意这一步可以用双指针(滑动窗口)的方法在均 摊O(1)的时间内找到，也可以用2分在O(logN)的时间内找到。

这时Ai一定在集合中，而Ai+1 ... Aj每一个都可以在或不在集合中，于是一共有2^(j-i)种 集合。这些集合是满足最小值是Ai的所有集合。

所以我们在枚举Ai的过程中求和即可。

总的时间复杂度是O(NlogN)。