目标
给你一个由正整数组成的数组 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。
由于数组长度不大，可以回溯枚举子序列，并针对每一子序列，两两比较，判断差的绝对值是否等于 k。
更好的处理方法是使用哈希表记录元素的出现次数，回溯枚举子序列时直接判断当前元素加减 k 的绝对值是否存在于哈希表中。
代码
/**
* @date 2025-03-07 0:09
*/
public class BeautifulSubsets2597 {
public int beautifulSubsets(int[] nums, int k) {
return dfs(0, new ArrayList<>(), nums, k);
}
public int dfs(int index, List<Integer> path, int[] nums, int k) {
if (index == nums.length) {
return path.size() > 0 ? 1 : 0;
}
int res = 0;
res += dfs(index + 1, path, nums, k);
for (Integer num : path) {
if (Math.abs(num - nums[index]) == k) {
return res;
}
}
path.add(nums[index]);
res += dfs(index + 1, path, nums, k);
path.remove(path.size() - 1);
return res;
}
}
性能
