class Solution {
public:
int beautifulSubsets(vector<int>& nums, int k) {
}
};
6352. 美丽子集的数目
给你一个由正整数组成的数组 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 <= 201 <= nums[i], k <= 1000原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 4.6 MB, 提交时间: 2023-03-19 22:22:12
func beautifulSubsets(nums []int, k int) int {
groups := map[int]map[int]int{}
for _, x := range nums {
if groups[x%k] == nil {
groups[x%k] = map[int]int{}
}
groups[x%k][x]++
}
ans := 1
for _, cnt := range groups {
m := len(cnt)
type pair struct{ x, c int }
g := make([]pair, 0, m)
for x, c := range cnt {
g = append(g, pair{x, c})
}
sort.Slice(g, func(i, j int) bool { return g[i].x < g[j].x })
f := make([]int, m+1)
f[0] = 1
f[1] = 1 << g[0].c
for i := 1; i < m; i++ {
if g[i].x-g[i-1].x == k {
f[i+1] = f[i] + f[i-1]*(1<<g[i].c-1)
} else {
f[i+1] = f[i] << g[i].c
}
}
ans *= f[m]
}
return ans - 1 // -1 去掉空集
}
java 解法, 执行用时: 5 ms, 内存消耗: 41 MB, 提交时间: 2023-03-19 22:21:59
class Solution {
public int beautifulSubsets(int[] nums, int k) {
var groups = new HashMap<Integer, TreeMap<Integer, Integer>>();
for (int x : nums)
groups.computeIfAbsent((x % k), key -> new TreeMap<>()).merge(x, 1, Integer::sum);
int ans = 1;
for (var g : groups.values()) {
int m = g.size();
var f = new int[m + 1];
f[0] = 1;
int i = 1, pre = 0;
for (var e : g.entrySet()) {
int cur = e.getKey();
if (i > 1 && cur - pre == k)
f[i] = f[i - 1] + f[i - 2] * ((1 << e.getValue()) - 1);
else
f[i] = f[i - 1] << e.getValue();
pre = cur;
++i;
}
ans *= f[m];
}
return ans - 1; // -1 去掉空集
}
}
python3 解法, 执行用时: 52 ms, 内存消耗: 14.8 MB, 提交时间: 2023-03-19 22:21:46
class Solution:
def beautifulSubsets(self, nums: List[int], k: int) -> int:
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
f[1] = 1 << g[0][1]
for i in range(1, m):
if g[i][0] - g[i - 1][0] == k:
f[i + 1] = f[i] + f[i - 1] * ((1 << g[i][1]) - 1)
else:
f[i + 1] = f[i] << g[i][1]
ans *= f[m]
return ans - 1 # -1 去掉空集
golang 解法, 执行用时: 68 ms, 内存消耗: 6.7 MB, 提交时间: 2023-03-19 22:19:34
func beautifulSubsets(nums []int, k int) int {
ans := -1 // 去掉空集
cnt := make([]int, 1001+k*2) // 用数组实现比哈希表更快
var dfs func(int)
dfs = func(i int) {
if i == len(nums) {
ans++
return
}
dfs(i + 1) // 不选
x := nums[i] + k // 避免负数下标
if cnt[x-k] == 0 && cnt[x+k] == 0 {
cnt[x]++ // 选
dfs(i + 1)
cnt[x]-- // 恢复现场
}
}
dfs(0)
return ans
}
golang 解法, 执行用时: 56 ms, 内存消耗: 6.7 MB, 提交时间: 2023-03-19 22:19:19
func beautifulSubsets(nums []int, k int) int {
ans := -1 // 去掉空集
cnt := make([]int, 1001+k*2)
var dfs func(int)
dfs = func(i int) { // 从 i 开始选
ans++ // 合法子集
if i == len(nums) {
return
}
for j := i; j < len(nums); j++ { // 枚举选哪个
x := nums[j] + k // 避免负数下标
if cnt[x-k] == 0 && cnt[x+k] == 0 {
cnt[x]++ // 选
dfs(j + 1)
cnt[x]-- // 恢复现场
}
}
}
dfs(0)
return ans
}
java 解法, 执行用时: 57 ms, 内存消耗: 41 MB, 提交时间: 2023-03-19 22:19:08
class Solution {
private int[] nums, cnt;
private int k, ans = -1; // 去掉空集
public int beautifulSubsets(int[] nums, int k) {
this.nums = nums;
this.k = k;
cnt = new int[k * 2 + 1001]; // 用数组实现比哈希表更快
dfs(0);
return ans;
}
// 从 i 开始选
private void dfs(int i) {
++ans; // 合法子集
if (i == nums.length)
return;
for (int j = i; j < nums.length; ++j) { // 枚举选哪个
int x = nums[j] + k; // 避免负数下标
if (cnt[x - k] == 0 && cnt[x + k] == 0) {
++cnt[x]; // 选
dfs(j + 1);
--cnt[x]; // 恢复现场
}
}
}
}
java 解法, 执行用时: 52 ms, 内存消耗: 41.5 MB, 提交时间: 2023-03-19 22:18:58
class Solution {
private int[] nums, cnt;
private int k, ans = -1; // 去掉空集
public int beautifulSubsets(int[] nums, int k) {
this.nums = nums;
this.k = k;
cnt = new int[k * 2 + 1001]; // 用数组实现比哈希表更快
dfs(0);
return ans;
}
private void dfs(int i) {
if (i == nums.length) {
ans++;
return;
}
dfs(i + 1); // 不选
int x = nums[i] + k; // 避免负数下标
if (cnt[x - k] == 0 && cnt[x + k] == 0) {
++cnt[x]; // 选
dfs(i + 1);
--cnt[x]; // 恢复现场
}
}
}
python3 解法, 执行用时: 2644 ms, 内存消耗: 16.2 MB, 提交时间: 2023-03-19 22:18:44
# 回溯（枚举选哪个）
class Solution:
def beautifulSubsets(self, nums: List[int], k: int) -> int:
ans = -1 # 去掉空集
cnt = [0] * (max(nums) + k * 2) # 用数组实现比哈希表更快
def dfs(i: int) -> None: # 从 i 开始选
nonlocal ans
ans += 1
if i == len(nums):
return
for j in range(i, len(nums)): # 枚举选哪个
x = nums[j]
if cnt[x - k] == 0 and cnt[x + k] == 0:
cnt[x] += 1 # 选
dfs(j + 1)
cnt[x] -= 1 # 恢复现场
dfs(0)
return ans
python3 解法, 执行用时: 3248 ms, 内存消耗: 16.1 MB, 提交时间: 2023-03-19 22:18:23
# 回溯（选或不选）
class Solution:
def beautifulSubsets(self, nums: List[int], k: int) -> int:
ans = -1 # 去掉空集
cnt = [0] * (max(nums) + k * 2) # 用数组实现比哈希表更快
def dfs(i: int) -> None:
if i == len(nums):
nonlocal ans
ans += 1
return
dfs(i + 1) # 不选
x = nums[i]
if cnt[x - k] == 0 and cnt[x + k] == 0:
cnt[x] += 1 # 选
dfs(i + 1)
cnt[x] -= 1 # 恢复现场
dfs(0)
return ans