美丽子集的数目

题目

6352. 美丽子集的数目

---

给你一个由正整数组成的数组 nums 和一个 正 整数 k 。

如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。

返回数组 nums 中 非空 且 美丽 的子集数目。

nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

示例 1：

输入：nums = [2,4,6], k = 2
输出：4
解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。
可以证明数组 [2,4,6] 中只存在 4 个美丽子集。

示例 2：

输入：nums = [1], k = 1
输出：1
解释：数组 nums 中的美丽数组有：[1] 。
可以证明数组 [1] 中只存在 1 个美丽子集。

提示：

• 1 <= nums.length <= 20
• 1 <= nums[i], k <= 1000

题解

方法一：

思路

枚举子集

用dfs枚举，并用哈希表记录已枚举元素，当前为x，存在x-k或x+k则剪枝，时间复杂度$O(2^n)$

用二进制枚举，需要$O(n)$检查子集元素中是否存在差值为k的两个元素，时间复杂度$O(n2^n)$

代码

class Solution {
public:
    #define N 5005
    int vis[N];
    
    int beautifulSubsets(vector<int>& nums, int k) {
        memset(vis, 0, sizeof(vis));
        int n = nums.size(), ans = 0;
        function<void(int)> dfs = [&](int i) {
            if (i == n) {
                ans++;
                return ;
            }
            dfs(i+1);
            if ((nums[i]-k<0 || vis[nums[i]-k]==0) && (nums[i]+k>=N || vis[nums[i]+k]==0)) {
                vis[nums[i]]++;
                dfs(i+1);
                vis[nums[i]]--;
            }
        };
        dfs(0);
        return ans-1;
    }
};

方法二：

思路

将n个数模k分组。

任何不同组中的两个数不会形成差值为k。所以我们可以单独求出每个组中的合法子集，然后根据乘法原理累乘起来即可。

每一组中相邻两个数是的差是k的倍数。我们它们排序去重得到a，并统计每个数出现的个数cnt。

观察到只有相邻两个数才会出现差值为k，考虑用dp。定义$f_{i}$为前i个数可以选出的合法子集个数。

对于前i个数可构成的子集分为包含第i个数和不包含第i个数。

当不包含第i个数时，则规模转为前n-1个数构成的合法子集。

当包含第i个数时，需要考虑第i个和第i-1个的差值是否为k。

• 若差值为k，则我们不能选择第i-1个值。所以只能从前i-2个数中选子集。
• 若差值不为k，则可以从前i-1个数中选子集。

注意包含第i个数时，由于第i个数出现的次数是$cnt_i$。所以可以选取这$cnt_i$个数的非空子集$2^{cnt_i}-1$。

所以状态转移方程为:

• $f_i = f_{i-1} + f_{i-2}*(2^{cnt_i-1}), a_i = a_{i-1}+k$
• $f_i = f_{i-1}*(2^{cnt_i}), a_i != a_{i-1}+k$

边界状态$f_{0} = 2^{cnt_0}, f_{-1} = 1$

代码

class Solution {
public:
    int beautifulSubsets(vector<int>& nums, int k) {
        map<int,map<int,int>> mp; // mp[i][j] 第i组中j出现的次数。
        for (int i:nums) {
            mp[i%k][i]++;
        }
        int ans = 1;
        for (auto& [i,j]:mp) {
            int n = j.size();
            vector<pair<int,int>> a(j.begin(), j.end());
            vector<int> f(n);
            function<int(int)> dfs = [&](int p) {
                if (p<0) return 1;
                if (p == 0) return (1<<a[p].second);
                if (f[p]) return f[p];
                if (a[p].first == a[p-1].first+k) {
                    return f[p] = dfs(p-1) + dfs(p-2)*((1<<a[p].second)-1);
                } else {
                    return f[p] = dfs(p-1)*(1<<a[p].second);
                }
            };
            ans *= dfs(n-1);
        }
        return ans-1;
    }
};