可生成唯一子集和的ID序列术语、构造及反解方法咨询

你描述的这种任意子集的和完全唯一的数列，广义上称为唯一子集和序列。而工程场景下最常用的可低成本构造的该类序列，专有名称为超递增序列（Superincreasing sequence），其定义为：序列中每一项的数值，都大于前面所有项的数值总和，这个特性天然保证了任意子集的和不会和其他子集重复。

超递增序列的生成规则非常简单，完全可以直接套用：

• 首项取值为 a₁ = 1
• 第n项的取值满足规则：aₙ > sum(a₁, a₂, ..., aₙ₋₁)
  工程上最常用的简化实现是直接使用2的幂次生成ID，公式为：aₙ = 2^(n-1)，生成的序列为1、2、4、8、16、32……以此类推。这种生成方式不需要额外计算校验，天生满足超递增要求，和值还可以直接对应二进制位状态，后续处理效率极高。

小提示：如果你的分类数量不超过32个，所有组合的和值都可以用32位整型存储；不超过64个则用64位整型存储即可，分类数量更多时可使用变长整数类型存储。

由于我们使用的是超递增序列，不需要复杂的动态规划或穷举，使用贪心遍历法就能实现最高效的反推，时间复杂度仅为O(n)（n为全部分类的数量），如果提前终止甚至可以优化到O(k)（k为选中的分类数量），步骤如下：

1. 提前把全量分类ID按从小到大的顺序排序
2. 初始化剩余和值为传入的总求和值，初始化结果集为空
3. 从最大的ID开始倒序遍历所有ID：
   • 如果当前ID ≤ 剩余和值，说明该分类被选中，将其加入结果集，同时用剩余和值减去当前ID
   • 如果剩余和值变为0，直接终止遍历
4. 最终结果集就是参与求和的所有分类ID

对应的Python代码示例如下：

def get_selected_ids(total_sum: int, sorted_id_list: list) -> list:
    selected = []
    remaining = total_sum
    # 从大到小遍历已排序的ID列表
    for id_val in reversed(sorted_id_list):
        if id_val <= remaining:
            selected.append(id_val)
            remaining -= id_val
            if remaining == 0:
                break
    return selected

如果使用的是2的幂次生成的ID，还可以直接用位运算进一步加速，直接判断对应二进制位是否为1即可得到选中的分类。

内容的提问来源于stack exchange，提问作者drex