有多少非空Subsets满足最小+最大小于等于K？

// For a given vector of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K
// For example, for K = 8 and vector [2, 4, 5, 7], the solution is 5 ([2], [4], [2, 4], [2, 4, 5], [2, 5])

The time complexity should be O(N²). Approach and code was asked

题目没说但是我猜：虽然每个subsets里可以有重复，但应该会要求subsets S和其它subsets不能重复。不知道有无N LogN 的解法。

比如对于 [1,1,3,3,3,2,2,9] K=5，应该有：35种
f(1,1)=2
f(1,2)=4
f(1,3)=18
f(2,2)=2
f(2,3)=6
f(3,3)=3

面试人虽然说2,4,5,7， K=8有5种。但我怎么感觉有7种？([2], [2, 4], [2, 4, 5], [2, 5], [4], [5], [7])
f(2,2)=1
f(2,4)=1
f(2,5)=2f(4,4)=1
f(5,5)=1
f(7,7)=1

改正：

对于 [1,1,3,3,3,2,2,9] K=5，应该有：32种
f(1,1)=2
f(1,2)=4
f(1,3)=18
f(2,2)=2
f(2,3)=6
f(3,3)=0 因为3+3 > K

对于[2,4,5,7]， K=8的确是有5种。([2], [2, 4], [2, 4, 5], [2, 5], [4])f(5,5)=0 因为5+5 > K
f(7,7)=0 因为7+7 > K

lz是刚参加完微软onsite么...

Leoaqr 发表于 2019-2-25 15:34
lz是刚参加完微软onsite么...

不是。在careercup上这是道新题，标注的tag是谷歌。没想到微软也测这题。

瞎逼逼几句：
既然是subsets，那么就和顺序无关了。
先排序，去重（统计每个数的个数）
枚举最小值m，然后找到最大的小于等于(K-m)的那个数M，那么集合中m必选，m与M之间的数的所有组合都满足要求，2的幂
此外，由于枚举的是最小值，m不断变大，那么M是不断变小的，找M的复杂度总共为O(N)
细节注意下就好
复杂度大概就是排序的复杂度了？

比如 [ 2, 4, 5, 7 ] :
- 枚举 2 ，找到 5 ，那么就把[ 4, 5 ]随意组合，有 2^2=4 种：　[ 2 ] [ 2 4 ] [ 2 5 ] [ 2 4 5 ]
- 枚举 4 ，找到 4 ，那么就把[ 空 ]随意组合，有2^0=1种： [ 4 ]
- 枚举 5 ，找到 2 ，但此时5不再是最小值，结束
一共有 4+1=5 种