【Leetcode 每日一题】2597. 美丽子集的数目

问题背景

给你一个由正整数组成的数组 $nums$ 和一个 正 整数 $k$。
如果 $nums$ 的子集中，任意两个整数的绝对差均不等于 $k$，则认为该子数组是一个 美丽 子集。
返回数组 $nums$ 中 非空 且 美丽 的子集数目。
$nums$ 的子集定义为：可以经由 $nums$ 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

数据约束

• $1\le nums.length\le 18$
• $1\le nums[i],k\le 1000$

解题过程

在求 子集 的基础上，额外去掉可能导致差值为 $k$ 的情况即可。

具体实现

class Solution {private int res = -1;public int beautifulSubsets(int[] nums, int k) {Map<Integer, Integer> count = new HashMap<>();dfs(0, nums, k, count);return res;}private void dfs(int i, int[] nums, int k, Map<Integer, Integer> count) {if (i == nums.length) {res++;return;}dfs(i + 1, nums, k, count);int cur = nums[i];if (count.getOrDefault(cur - k, 0) == 0 && count.getOrDefault(cur + k, 0) == 0) {count.merge(cur, 1, Integer::sum);dfs(i + 1, nums, k, count);count.merge(cur, -1, Integer::sum);}}
}