330

第一次试错

根据题目和范围推出可以logn, 但想的时候出了差错，想到的条件如下

1. 得到从 [1, curr] 的 sums，我们可以观察到从 [1, curr] 到 subsets 的和中出现 [1, sums] 区间每一个数
2. 如果下一个数 < sums 直接加入，否则加curr + 1直到满足 sums > 该数为止
3. 最多 $n(n+1)/2 >= 2^31 - 1$ 约1e6 于是我直接使用了set记录已经存在的值，然后从1开始加到1e6并判断条件

第二次试错

发现错了以后重新观察了一下条件，第一点完全没有问题，但第二点有问题，因为从1可以推出绝大多数情况curr + 1是在sums内的，所以2直接改成加 sums + 1即可，所以条件变成了

1. 得到从 [1, curr] 的 sums，我们可以观察到从 [1, curr] 到 subsets 的和中出现 [1, sums] 区间每一个数
2. 如果下一个数 < sums 直接加入，否则加sums + 1直到满足 sums > 该数为止
3. 最多 n(n+1)/2 >= 2**31 - 1 约1e6 subsets的和中出现 [1, sums] 区间的每一个数

第三次试错

还是错的，根本不需要用set， 因为不需要看curr + 1，应该直接观察数组的 nums[i ]。这个时候我发现 nums[i] = sums + 1的情况我们也可以加进去，于是得到

1. 从数组中加值得到从 [1, curr] 的 sums，我们可以观察到从 [1, curr] 到 subsets 的和中出现 [1, sums] 区间每一个数
2. 如果当前数组值 nums[i] <= sums + 1 直接加入，否则加sums + 1直到满足 sums > 该数为止
3. 因为是倍增所以 n 最后得到了正确结果