非负权重对象TopK子集：把最大和转成最小排除代价

题目重点：相同权重对象仍是不同身份，等和结果保留多个子集。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

对象权重非负；全部子集含空集，最多返回min(K,2^n)。训练输出mask身份按权重排序后的稳定位置。
负权重会改变以全选为最大起点的证明，不能直接使用此代码。

解题路线

全选sum(weights)为最大。每个选择子集对应一个排除子集，选和=总和−排除和，因此枚举最小排除代价。
权重升序，每堆状态记录排除集合及其最大下标i。生成两子：加入i+1，或把i替成i+1；这构成所有非空排除子集的唯一父树。根为空排除。
子代价不小于父代价（加入非负、替换更大权重），最小堆按代价弹出正是最大选择和顺序。等权/零权不能用sum去重，因为多个身份子集都合法。

手动走一遍

weights[1,2]最大子集和按3、2、1、0；对应排除0、1、2、3。weights[0,0]有四个不同子集都和0，K4必须返回四个不同mask。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from heapq import heappush,heappop


def largest_subsets(weights,k):
    if k<0 or any(x<0 for x in weights):raise ValueError("nonnegative weights and k required")
    # The returned mask uses positions in this sorted list; retain original IDs if required.
    weights=sorted(weights);total=sum(weights);n=len(weights);heap=[(0,-1,0)];result=[]
    while heap and len(result)<k:
        penalty,i,mask=heappop(heap)
        result.append((total-penalty,((1<<n)-1)^mask))
        nxt=i+1
        if nxt<n:
            heappush(heap,(penalty+weights[nxt],nxt,mask|1<<nxt))
            if i>=0:heappush(heap,(penalty-weights[i]+weights[nxt],nxt,(mask^(1<<i))|(1<<nxt)))
    return result

复杂度

排序O(nlogn)，K次堆弹推O(KlogK)，堆O(K)，mask有n位的大整数，位操作/存储需另计而非无限n下真O(1)。返回文本化成员还需按成员数计输出。

易错点与追问

容易失分的边界

把所有相同总和去重会丢对象身份。
heap只加下一项没有替换分支，会漏例如排除{下标1}但不排除0。

继续深挖

保留原始ID时怎样携带排序映射？
权重可负时怎样先选所有正项并按翻转代价重建子集身份？