美丽子集的数目

题解的核心思想是通过模 k 的分组来识别可能的冲突，即当两个数的差为 k 时，它们在同一个模 k 的组内的位置之间相差 1。算法首先通过模 k 对 nums 中的数字进行分组，并使用 Counter 来统计同一组内每个数出现的次数。对每个组内的数字进行排序，然后使用动态规划计算每组内可以形成的美丽子集数目。对于每组，如果两个数之间的差为 k，则在计算子集时需要考虑不选取前一个数的情况。最后，所有组的子集数目相乘（去除空集的情况）即为结果。

时间复杂度: O(n^2)

空间复杂度: O(n)

from collections import Counter, defaultdict
class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        # 使用 defaultdict 和 Counter 对 nums 数组按照 mod k 的值进行分组和计数
        groups = defaultdict(Counter)
        for x in nums:
            groups[x % k][x] += 1

        ans = 1 # 初始化答案
        # 遍历每个组，计算每个组的美丽子集数
        for cnt in groups.values():
            # 对当前组内的元素进行排序
            g = sorted(cnt.items())
            m = len(g) # 组内元素数量
            f = [0] * (m+1) # 动态规划数组，用于计算子集数
            f[0] = 1 # 空集的子集数为1
            f[1] = 2**g[0][1] # 只包含第一个元素的子集数
            for i in range(1, m):
                # 判断当前元素与前一个元素的差是否为 k
                if g[i-1][0] == g[i][0]-k:
                    f[i+1] = f[i] + f[i-1] * (2**g[i][1]-1)
                else:
                    f[i+1] = f[i] * 2**g[i][1] # 如果差不为 k，则可以自由组合
            ans *= f[m] # 将当前组的结果乘入总答案
        return ans - 1 # 减去空集