题解

核心算法

降序排序，预处理后缀和；搜索选/不选，并用当前个数、剩余总和剪枝。

思路推导

搜索覆盖每个子集；达标时更新全局最优，不能达标的分支由上界安全排除。

正确性说明

按照上述状态含义与转移顺序，每一步只使用已经正确求出的子问题；所有合法情况被完整计入，且互斥分类不会重复计数，因此最终输出即为题目所求。

复杂度

• 时间复杂度：最坏 O(2^n)
• 空间复杂度：O(n)

易错点

后缀和是“最好还能增加多少”，不能用错方向。

完整标程见 std/main.cpp。