526互联

[LeetCode] 2597. The Number of Beautiful Subsets

发布时间 2023-07-19 04:01:05作者: CNoodle

You are given an array nums of positive integers and a positive integer k.

A subset of nums is beautiful if it does not contain two integers with an absolute difference equal to k.

Return the number of non-empty beautiful subsets of the array nums.

A subset of nums is an array that can be obtained by deleting some (possibly none) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.

Example 1:

Input: nums = [2,4,6], k = 2
Output: 4
Explanation: The beautiful subsets of the array nums are: [2], [4], [6], [2, 6].
It can be proved that there are only 4 beautiful subsets in the array [2,4,6].

Example 2:

Input: nums = [1], k = 1
Output: 1
Explanation: The beautiful subset of the array nums is [1].
It can be proved that there is only 1 beautiful subset in the array [1]. 

Constraints:

  • 1 <= nums.length <= 20
  • 1 <= nums[i], k <= 1000

美丽子集的数目。

给你一个由正整数组成的数组 nums 和一个 正 整数 k 。

如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。

返回数组 nums 中 非空 且 美丽 的子集数目。

nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/the-number-of-beautiful-subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是回溯。这道题算是78题子集的变种，在求 nums 数组所有不同子集的同时，需要确保

  • 子集不能为空
  • 子集之间的任意两个元素之间的差值 != k

注意这里我们需要用一个 hashmap 记录遇到的元素，因为有可能 input 数组里有重复元素。

时间O(2^n) - 和子集的复杂度一样

空间O(n)

Java实现

 1 class Solution {
 2     private HashMap<Integer, Integer> map = new HashMap<>();
 3     private int res;
 4 
 5     public int beautifulSubsets(int[] nums, int k) {
 6         helper(nums, k, 0);
 7         return res;
 8     }
 9 
10     private void helper(int[] nums, int k, int start) {
11         if (map.size() != 0) {
12             res++;
13         }
14         for (int i = start; i < nums.length; i++) {
15             if (map.containsKey(nums[i] - k) || map.containsKey(nums[i] + k)) {
16                 continue;
17             }
18             map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
19             helper(nums, k, i + 1);
20             map.put(nums[i], map.get(nums[i]) - 1);
21             if (map.get(nums[i]) == 0) {
22                 map.remove(nums[i]);
23             }
24         }
25     }
26 }

 

LeetCode 题目总结