Leetcode-每日一题2597.-美丽子集的数目
目录
【Leetcode 每日一题】2597. 美丽子集的数目
问题背景
给你一个由正整数组成的数组
n u m s nums
n
u
m
s 和一个 正 整数
k k
k 。
如果
n u m s nums
n
u
m
s 的子集中，任意两个整数的绝对差均不等于
k k
k ，则认为该子数组是一个 美丽 子集。
返回数组
n u m s nums
n
u
m
s 中 非空 且 美丽 的子集数目。
n u m s nums
n
u
m
s 的子集定义为：可以经由
n u m s nums
n
u
m
s 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。
数据约束
1 ≤ n u m s . l e n g t h ≤ 18 1 \le nums.length \le 18
1
≤
n
u
m
s
.
l
e
n
g
t
h
≤
18
1 ≤ n u m s [ i ] , k ≤ 1000 1 \le nums[i], k \le 1000
1
≤
n
u
m
s
[
i
]
,
k
≤
1000
解题过程
在求 的基础上，额外去掉可能导致差值为
k k
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);
}
}
}