[LeetCode] 每日一题 2597. 美丽子集的数目

题目链接

https://leetcode.cn/problems/the-number-of-beautiful-subsets

题目描述

给你一个由正整数组成的数组 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 <= 18

• 1 <= nums[i], k <= 1000

解题思路

今天的题目要求我们计算一个数组中美丽子集的数量，所谓美丽子集是指数组中的任意两个整数的绝对差不等于给定的整数 k。这道题目可以使用回溯的思路来解决，具体方法如下：

1. 回溯思路
   我们可以通过回溯来尝试在每个元素上做选择：每次遍历到一个元素时，有两种选择：

   • 包含该元素

   • 不包含该元素
     需要注意的是，在选择包含该元素时，我们需要确保该元素与当前已经选择的任何元素的差值不等于 k

2. 状态管理
   使用一个哈希表 count 来记录当前已经选择的元素。如果当前选择的元素 x 和 x-k 或 x+k 其中一个已经出现在子集中，那么就不能选择该元素。否则，可以选择该元素，并继续递归处理下一个元素

3. 递归过程
   递归从数组的第一个元素开始，逐个考虑每个元素是否加入当前子集。递归过程中，如果选择某个元素加入子集，就更新哈希表，并在递归完成后撤回该选择，继续考虑下一个元素

4. 结束条件
   当遍历完所有元素时，递归结束。每次递归到末尾时，如果当前的子集符合条件，就将答案加一

代码实现

class Solution {
    int ans = -1;

    public int beautifulSubsets(int[] nums, int k) {
        HashMap<Integer, Integer> count = new HashMap<>();
        dfs(0, nums, k, count);
        return ans;
    }

    private void dfs(int i, int[] nums, int k, HashMap<Integer, Integer> count) {
        if (i == nums.length) {
            ans++;
            return;
        }
        dfs(i + 1, nums, k, count);
        int x = nums[i];
        if (count.getOrDefault(x - k, 0) == 0 && count.getOrDefault(x + k, 0) == 0) {
            count.merge(x, 1, Integer::sum);
            dfs(i + 1, nums, k, count);
            count.merge(x, -1, Integer::sum);
        }
    }
}

复杂度分析

• 时间复杂度：回溯的时间复杂度是 O(2^n)，其中 n 是数组 nums 的长度，因为每个元素都有两种选择：选或者不选。因此，整体的时间复杂度是 O(2^n)

• 空间复杂度：递归调用栈的最大深度为 O(n)，此外，我们还使用了一个哈希表 count 来存储当前子集中的元素，最坏情况下哈希表的大小也是 O(n)。因此，空间复杂度是 O(n)

总结

这道题目考察了回溯算法和状态管理的技巧，核心思想是通过回溯逐个元素决定是否加入子集，并通过哈希表确保子集满足绝对差不等于 k 的条件。回溯的过程虽然可以暴力遍历所有子集，但通过合理的剪枝，能够在一定程度上减少不必要的计算。对于类似的组合问题，回溯是一种非常有效的解决策略

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。