2597. 美丽子集的数目

发表于 2026-01-07 分类于力扣阅读次数： Waline：本文字数： 3.5k 阅读时长 ≈ 12 分钟

考点

数学
同余
线性DP
搜索
排列组合

思路

目标：给定数组 nums 与整数 k，统计满足 任意两元素差值不等于 k 的 非空子集 个数。约束等价表述：若子集中选了值 x（至少一个 x），则不能再选值 x-k 与 x+k。

0. 统一建模：冲突图 + 加权独立集计数

将“不能同时出现差为 k 的两数”抽象为图约束：

将每个“数值”视作一个点（注意数组里可以有重复值）。
若两个数值相差恰好 k，则二者之间连一条边（互斥边）。
子集合法 ⇔ 选出的点集合中 没有边的两端同时被选 ⇔ 这是一个 独立集。

重复值如何处理？

若某个值 v 在 nums 中出现 cnt(v) 次，则从这些重复元素中：
- 不选 v：1 种
- 选 v：可以选任意非空子集，共 \(2^{cnt(v)}-1\) 种
因此“是否选择值 v”是一个二元决策，但“选择时的方案数”是一个权重。

这四份代码分别对应：

直接在下标层面做子集回溯（输入视角：选/不选）。
在答案层面做子集回溯（答案视角：从候选里挑下一个）。
利用同余分组拆图 + 在每组做“打家劫舍”DP。
用“最长连续序列”的链起点思想，把第 3 种进一步优化为线性扫链 DP。

1) 写法一：子集型回溯（输入视角，逐位置“选或不选”）

1.1 状态设计与不变量

定义递归 dfs(i) 表示：正在处理下标 i，前面 0..i-1 的元素已经做出选择（选或不选），并用 mp 记录当前子集中 各数值出现次数。

不变量（递归进入 dfs(i) 时成立）：

mp[v] 等于当前选择路径中值 v 被选了多少次；
当前路径对应的子集一定满足约束：不存在差为 k 的两值同时出现。

1.2 转移（选/不选）

对 nums[i] = x：

不选：直接 dfs(i+1)
选：仅当 x-k 与 x+k 当前都未被选（次数为 0）即 mp[x-k]==0 && mp[x+k]==0 时，做：
- mp[x]++
- dfs(i+1)
- 回溯 mp[x]--

终止条件：i == n，说明对每个位置都做完决策，此时得到一个完整子集，计数加一。

1.3 正确性要点（为什么不会重计/漏计）

每个下标位置只做一次“选/不选”，因此每条根到叶路径对应唯一的子集（按下标决定）。
剪枝条件确保每次“选”都不会破坏约束；回溯恢复状态确保不同分支互不干扰。

1.4 复杂度

最坏时间：\(O(2^n)\)（每个元素两种选择）
空间：递归栈 \(O(n)\)；哈希表最多存储访问到的值（本写法使用 operator[] 可能插入键，键数会增长，但仍受 \(O(n)\) 量级限制）。

1.5 代码（加注释）

class Solution {
public:
    int ans = 0;
    unordered_map<int, int> mp; // mp[v]：当前子集中值 v 的出现次数

    // dfs(i)：处理下标 i 及其之后元素的选择
    void dfs(int i, vector<int>& nums, int k) {
        // 处理完所有位置，得到一个完整子集
        if (i == (int)nums.size()) {
            ++ans;
            return;
        }

        // 1) 不选 nums[i]
        dfs(i + 1, nums, k);

        // 2) 尝试选 nums[i]
        int x = nums[i];
        // 只有当 x-k 与 x+k 都未出现时，才允许选 x
        // 这里用 mp[...] 会在不存在键时插入默认 0；逻辑上是安全的
        if (mp[x - k] == 0 && mp[x + k] == 0) {
            mp[x]++;                 // 选入 x
            dfs(i + 1, nums, k);     // 继续处理下一位置
            mp[x]--;                 // 回溯：撤销选择
        }
    }

    int beautifulSubsets(vector<int>& nums, int k) {
        dfs(0, nums, k);
        return ans - 1; // 去掉空集
    }
};

2) 写法二：子集型回溯（答案视角，从候选集合中“挑下一个”）

2.1 与写法一的区别：状态含义变为“下一个可选起点”

写法二把“子集生成”的过程改为：

递归状态 dfs(i)：表示当前子集已经确定（由 mp 记录），接下来允许从下标区间 [i, n) 中继续选择元素作为扩展。
在 dfs(i) 处，先把当前子集计入答案（++ans），然后枚举下一个要加入的元素。

这是一种典型的“组合枚举模板”：通过保证下标递增（递归进入 dfs(j+1)），确保每个子集只被生成一次。

2.2 为什么在函数开头 `++ans` 合法

在这种答案视角写法中：

每次进入 dfs(i)，mp 对应一个合法子集（可能为空），应计数 1 次。
然后通过选择后续元素扩展该子集，形成更大的子集。

关键前提：不同路径不会到达同一个 mp 状态（否则会重计）。递归只从 j+1 往后选，天然保证“每个下标集合只出现一次”，因此每个子集只会计数一次。

2.3 复杂度

最坏仍是 \(O(2^n)\)（枚举所有子集），但常数往往更好（剪枝后对深度较小子集也计数，不必到叶子才计数）。
空间同写法一。

2.4 代码（加注释）

class Solution {
public:
    int ans = 0;
    unordered_map<int, int> mp; // mp[v]：当前子集中值 v 的出现次数

    // dfs(i)：当前子集已确定，下一次可从下标 [i, n) 中挑一个元素加入
    void dfs(int i, vector<int>& nums, int k) {
        ++ans; // 当前 mp 对应的子集（含空集）计数一次

        if (i == (int)nums.size())
            return;

        // 枚举“下一个要加入子集的元素”的下标 j
        for (int j = i; j < (int)nums.size(); j++) {
            int x = nums[j];

            // 检查加入 x 是否会与已选的 x-k 或 x+k 冲突
            if (mp[x - k] == 0 && mp[x + k] == 0) {
                mp[x]++;              // 选择 nums[j]
                dfs(j + 1, nums, k);  // 下一次只能从 j+1 之后选，避免重复计数
                mp[x]--;              // 回溯
            }
        }
    }

    int beautifulSubsets(vector<int>& nums, int k) {
        dfs(0, nums, k);
        return ans - 1; // 去掉空集
    }
};

3) 写法三：同余分组 + 乘法原理 + “打家劫舍”动态规划

回溯能 AC 的前提往往是 n 不大；而这道题的结构其实允许把指数问题拆成多个小链的乘积，从而做到近线性/近排序复杂度。

3.1 同余分组的核心结论

若两个数差为 k： \[ a-b = \pm k \ \Rightarrow\ a \equiv b \pmod{k} \] 因此产生冲突的两值必在同一个模类中。把所有数按 x % k 分组后：

不同组之间：绝无冲突，选择相互独立
同一组内：才需要处理差为 k 的互斥关系

于是全局答案可以用乘法原理： \[ \text{TotalWays} = \prod_{r=0}^{k-1} \text{Ways}(r) \] 其中 \(\text{Ways}(r)\) 表示余数为 \(r\) 的那一组内部能形成的合法子集方案数（包含空集）。

3.2 组内“压缩重复值”与权重

对组内每个不同值 v，出现次数为 cnt(v)：

对 v 的选择方式总数（包含不选）为： \[ 2^{cnt(v)} \]
若规定“必须选 v”（至少选一个），则方式数为： \[ 2^{cnt(v)} - 1 \]

3.3 为什么组内变成“打家劫舍”链

把同一余数组内的不同值排序： \[ v_1 < v_2 < \cdots < v_m \] 由于同余，潜在冲突只发生在差为 k 的相邻层级上。对任意 i：

若 \(v_i - v_{i-1} = k\)，则 v_i 与 v_{i-1} 互斥（不能同时被选）。
若差不等于 k，则二者完全独立。

这与“打家劫舍”完全一致：相邻（在冲突边意义下）不可同时取，只是每个点有权重（取该点的方式数）。

3.4 DP 设计与递推

令 f[i] 表示：考虑前 i 个不同值（排序后），可形成的合法子集方案数（包含空集）。

设第 i 个值出现 cnt_i 次，则该值的“总选择方式数”为 \(2^{cnt_i}\)，“非空选择方式数”为 \(2^{cnt_i}-1\)。

初始： \[ f[0] = 1 \]

\[ f[1] = 2^{cnt_1} \]
对 \(i \ge 2\)：
- 若 \(v_i - v_{i-1} = k\)（冲突）：
  - 不选 \(v_i\)：贡献 \(f[i-1]\)
  - 选 \(v_i\)：必须保证 \(v_{i-1}\) 不选，因此回到 \(f[i-2]\)，且 \(v_i\) 的选择必须非空： \[ f[i] = f[i-1] + f[i-2]\cdot(2^{cnt_i}-1) \]
- 若 \(v_i - v_{i-1} \ne k\)（独立）： \[ f[i] = f[i-1]\cdot 2^{cnt_i} \]

最后该组的方案数为 \(f[m]\)。

3.5 复杂度

分组统计：\(O(n)\)
每组用 map 自动排序并遍历：总 \(O(n \log n)\)
DP：总 \(O(n)\)

整体约为 \(O(n \log n)\)，远优于回溯的指数复杂度。

3.6 代码（加注释）

class Solution {
public:
    int beautifulSubsets(vector<int>& nums, int k) {
        // mp[r][v] = cnt：余数 r 的组里，值 v 出现次数 cnt
        unordered_map<int, map<int, int>> mp;
        for (int x : nums)
            mp[x % k][x]++;

        int ans = 1; // 全局乘法原理：各组相互独立，方案数相乘

        for (auto& [_, cnt] : mp) {   // cnt 是一个有序 map：value -> frequency
            int n = (int)cnt.size();  // 该组内不同值的个数
            vector<int> f(n + 1);

            auto it = cnt.begin();

            // f[0] = 1：空集
            f[0] = 1;

            // f[1] = 2^{cnt_1}：对第一个值，要么不选(1)，要么选(2^{cnt_1}-1)
            f[1] = 1 << (it++->second);

            // 从第二个不同值开始做“打家劫舍”式 DP
            for (int i = 2; i <= n; ++i, it = next(it)) {
                int pre = prev(it)->first;      // 上一个值
                int cur = it->first;            // 当前值
                int count = it->second;         // 当前值出现次数
                int pow2 = 1 << count;          // 2^{count}

                if (cur - pre == k) {
                    // 冲突：要么不选 cur => f[i-1]
                    //      要么选 cur(非空) 且 pre 不选 => f[i-2] * (2^{count}-1)
                    f[i] = f[i - 1] + f[i - 2] * (pow2 - 1);
                } else {
                    // 无冲突：cur 与前面独立，直接乘以 2^{count}
                    f[i] = f[i - 1] * pow2;
                }
            }

            // 该组完成，乘到全局答案
            ans *= f[n];
        }

        return ans - 1; // 去掉全空选择（空集）
    }
};

4) 写法四：链起点扫描优化（借鉴“最长连续序列”思想）

请先会写128. 最长连续序列

写法三已经是经典 DP；写法四的优化点在于：不再显式按 mod k 分组和排序，而是直接在哈希表中找“链”的起点，然后沿着步长 k 扫描整条链，用滚动 DP 计算链的方案数。

这与“最长连续序列”（找 x-1 不存在的起点，然后沿 x+1 扩展）完全同构，只是步长从 1 变成 k。

4.1 为什么可以拆成若干条链相乘

考虑所有不同值构成的集合 \(V\)。定义边： \[ (v, v+k)\ \text{存在当且仅当}\ v\ \text{与}\ v+k\ \text{都出现在数组中} \] 则所有冲突关系构成若干条不相交的链（严格地说，是按步长 k 的算术级数连通分量，每个分量是一条路径图，因为每个点最多与 v-k、v+k 相连）。

不同连通分量之间没有约束，因此方案数相乘。

写法三通过“按余数分组 + 组内排序”来隐式得到这些链；写法四则通过“找链起点 + 顺着 +k 扫链”来显式遍历连通分量。

4.2 链起点的判定

某个值 key 是一条链的起点当且仅当：

key 存在
key - k 不存在

即：

1	if (mp.find(key - k) != mp.end()) continue; // 不是起点

这样能保证每条链只处理一次，不会重复乘入全局答案。

4.3 链上滚动 DP（与写法三完全一致，只是省掉数组 `f`）

链上值依次为： \[ a,\ a+k,\ a+2k,\ \ldots \] 令当前处理到链上的第 \(t\) 个点时：

f0 表示 \(f[t-1]\)（前一项）
f1 表示 \(f[t]\)（当前项）

对下一点（出现次数为 cnt_next）：

若选择该值（非空）：有 \(2^{cnt\_next}-1\) 种
递推与冲突情形一致（链上相邻必冲突）： \[ f[t+1] = f[t] + f[t-1]\cdot(2^{cnt\_next}-1) \]

写法四正是用 f2 = f1 + f0 * ((1<<cnt_next)-1) 实现这一点。

4.4 复杂度

建频次表：\(O(n)\)
每个不同值最多在某条链上被访问一次：总 \(O(|V|)\)
总体近似 \(O(n)\)

相对于写法三，去掉了 map 的排序开销。

4.5 代码（加注释）

class Solution {
public:
    int beautifulSubsets(vector<int>& nums, int k) {
        unordered_map<int, int> mp; // mp[v]：值 v 的出现次数
        for (int x : nums)
            mp[x]++;

        int ans = 1; // 全局乘积：每条链（连通分量）独立

        // 枚举每个不同值，尝试把它当作链的起点
        for (auto& [key, cnt] : mp) {
            // 如果 key-k 存在，则 key 不是起点（它在某条链的中间）
            auto it = mp.find(key - k);
            if (it != mp.end())
                continue;

            // 现在 key 是某条链的起点：key, key+k, key+2k, ...
            // 链上 DP 初始化：
            // f0 = f[0] = 1（空集）
            // f1 = f[1] = 2^{cnt(key)}（对第一个值：选或不选）
            int f0 = 1;
            int f1 = 1 << cnt;

            int ky = key;

            // 沿着 ky+k 扩展整条链
            while (mp.find(ky + k) != mp.end()) {
                int c = mp[ky + k];          // 下一个值的出现次数
                int pow2 = 1 << c;           // 2^{c}
                // 相邻必冲突（差 k）：
                // 新 f = f1（不选下一个） + f0 * (2^{c}-1)（选下一个且前一个不选）
                int f2 = f1 + f0 * (pow2 - 1);

                // 滚动更新
                ky += k;
                f0 = f1;
                f1 = f2;
            }

            // 一条链处理完毕，把该链的方案数乘到全局
            ans *= f1;
        }

        return ans - 1; // 去掉空集
    }
};

5) 四种写法对比与选型建议

5.1 思维路线对比

写法一：最“朴素”的子集决策树，从输入下标逐个做二元决策。
写法二：组合枚举模板化，把“当前子集”视作节点，从候选中挑下一个元素扩展。
写法三：识别冲突仅发生在同余类内，转化为多条链的乘积；链上用“打家劫舍”DP。
写法四：将写法三的“排序建链”改成“哈希找链起点 + 扫链”，进一步优化到近线性。

5.2 时间复杂度对比（定性）

方法	核心技术	最坏时间
写法一	回溯选/不选	\(O(2^n)\)
写法二	回溯枚举组合	\(O(2^n)\)
写法三	同余分组 + 排序 + 链 DP	\(O(n\log n)\)
写法四	起点扫链 + 滚动 DP	近 \(O(n)\)

5.3 统一正确性观（同一个递推在不同层级出现）

写法一/二：在“下标子集”层面直接保证互斥。
写法三/四：在“数值图”层面把互斥结构简化为链，核心递推始终是：

\[ f[i] = \begin{cases} f[i-1] + f[i-2]\cdot(2^{cnt_i}-1), & \text{相邻冲突（差 }k\text{）}\\ f[i-1]\cdot 2^{cnt_i}, & \text{独立（无冲突）} \end{cases} \]

写法四的“扫链”实际上是在每一条“相邻必冲突”的链上反复应用第一种递推。

考点

思路