LeetCode 2597. The Number of Beautiful Subsets

原题链接在这里：https://leetcode.com/problems/the-number-of-beautiful-subsets/description/

题目：

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

题解：

The question asks for number of subsets without two nums having an absolute difference equal to k.

We can group the nums by num % k, then only nums in one group can have absolute difference equal to k.

The nubmers in different group can't have difference equal to k.

Within one group, we need to sort them.

For the previous number and current number, if the difference is equal to k.

Then taking the current number can't take the previous number. 
If difference != k, then it doesn't matter.

The final result minus 1 to exlude the empty subset.

Time Complexity: O(nlogn + k).

AC Java:

 1 class Solution {
 2     public int beautifulSubsets(int[] nums, int k) {
 3         HashMap<Integer, TreeMap<Integer, Integer>> hm = new HashMap<>();
 4         for(int num : nums){
 5             hm.putIfAbsent(num % k, new TreeMap<>());
 6             TreeMap<Integer, Integer> tm = hm.get(num % k);
 7             tm.put(num, tm.getOrDefault(num, 0) + 1);
 8         }
 9 
10         int res = 1;
11         for(int key = 0; key < k; key++){
12             int pre = 0;
13             int exclude = 1;
14             int include = 0;
15             if(hm.containsKey(key)){
16                 for(int num : hm.get(key).keySet()){
17                     int v = (1 << hm.get(key).get(num)) - 1; // count of non-empty subsets
18                     if(pre + k == num){
19                         int ex = exclude;
20                         exclude = include + exclude;
21                         include = ex * v;
22                     }else{
23                         int ex = exclude;
24                         exclude = include + exclude;
25                         include = (ex + include) * v;
26                     }
27 
28                     pre = num;
29                 }
30 
31                 res *= (exclude + include);
32             }
33         }
34 
35         return res - 1; // minus 1 to exclude the empty subset.
36     }
37 }

类似House Robber.