题解

核心算法

按递增下标枚举下一项；记录位置、剩余个数与当前和，并做数量不足、和超界剪枝。

思路推导

递增下标保证每个组合只枚举一次。

正确性说明

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

复杂度

• 时间复杂度：O(C(n,k))
• 空间复杂度：O(k)

易错点

k=0 时空集合；正数条件才允许 sum>S 剪枝。

完整标程见 std/main.cpp。