解题思路
我们需要构造一个严格递增的正整数序列 a1<a2<⋯<an,满足所有数的按位或(共鸣融合)结果恰好等于给定的目标值 k。
算法的核心思想是:利用 k 的二进制表示中所有为 1 的位,枚举这些位的所有非空子集,每个子集对应的数值就是选中位的权重之和。这些数值具有以下性质:
- 个数:设 k 的二进制表示中共有 x 个 1。这些位可以生成 2x−1 个不同的正整数(对应非空子集)。
- 按位或:这 2x−1 个数的按位或正好等于 k,因为每一位为 1 的位至少在某一个子集中被选中。
- 单调性:若将 k 中为 1 的位按权重从小到大排列(即位置升序),并按照子集的二进制掩码从小到大的顺序生成数字,得到的序列是严格递增的,且最后一个数正好是 k(全部位都选中的子集)。