2597. The Number of Beautiful Subsets LeetCode Solution

In this guide, you will get 2597. The Number of Beautiful Subsets LeetCode Solution with the best time and space complexity. The solution to The Number of Beautiful Subsets problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. The Number of Beautiful Subsets solution in C++
4. The Number of Beautiful Subsets solution in Java
5. The Number of Beautiful Subsets solution in Python
6. Additional Resources

Problem Statement of The Number of Beautiful Subsets

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 <= 18
1 <= nums[i], k <= 1000

Complexity Analysis

• Time Complexity: O(n\log n + k)
• Space Complexity: O(n + k)

2597. The Number of Beautiful Subsets LeetCode Solution in C++

// e.g. nums = [2, 3, 4, 4], k = 2
//
// subset[0] = [2, 4, 4']
// subset[1] = [1]
// count = {2: 1, 4: 2, 1: 1}
//
// Initially, skip = len([]) = 0, pick = len([]) = 0
//
// * For values in subset[0]:
//   After 2:
//     skip = skip + pick = len([]) = 0
//     pick = (2^count[2] - 1) * (1 + skip + pick)
//          = len([[2]]) * len([[]])
//          = len([[2]]) = 1
//   After 4:
//     skip = skip + pick = len([[2]]) = 1
//     pick = (2^count[4] - 1) * (1 + skip)
//          = len([[4], [4'], [4, 4']]) * len([[]])
//          = len([[4], [4'], [4, 4']]) = 3
//
// * For values in subset[1]:
//   After 1:
//     skip = skip + pick
//          = len([[2], [4], [4'], [4, 4']]) = 4
//     pick = (2^count[1] - 1) * (1 + skip + pick)
//          = len([[1]]) * len([[], [2], [4], [4'], [4, 4']])
//          = len([[1], [1, 2], [1, 4], [1, 4'], [1, 4, 4']]) = 5
//
// So, ans = skip + pick = 9

class Solution {
 public:
  int beautifulSubsets(vector<int>& nums, int k) {
    constexpr int kMax = 1000;
    vector<int> count(kMax + 1);
    unordered_map<int, set<int>> modToSubset;

    for (const int num : nums) {
      ++count[num];
      modToSubset[num % k].insert(num);
    }

    int prevNum = -k;
    int skip = 0;
    int pick = 0;

    for (const auto& [_, subset] : modToSubset)
      for (const int num : subset) {
        const int nonEmptyCount = pow(2, count[num]) - 1;
        const int cacheSkip = skip;
        skip += pick;
        pick =
            nonEmptyCount * (1 + cacheSkip + (num - prevNum == k ? 0 : pick));
        prevNum = num;
      }

    return skip + pick;
  }
};
/* code provided by PROGIEZ */

2597. The Number of Beautiful Subsets LeetCode Solution in Java

// e.g. nums = [2, 3, 4, 4], k = 2
//
// subset[0] = [2, 4, 4']
// subset[1] = [1]
// count = {2: 1, 4: 2, 1: 1}
//
// Initially, skip = len([]) = 0, pick = len([]) = 0
//
// * For values in subset[0]:
//   After 2:
//     skip = skip + pick = len([]) = 0
//     pick = (2^count[2] - 1) * (1 + skip + pick)
//          = len([[2]]) * len([[]])
//          = len([[2]]) = 1
//   After 4:
//     skip = skip + pick = len([[2]]) = 1
//     pick = (2^count[4] - 1) * (1 + skip)
//          = len([[4], [4'], [4, 4']]) * len([[]])
//          = len([[4], [4'], [4, 4']]) = 3
//
// * For values in subset[1]:
//   After 1:
//     skip = skip + pick
//          = len([[2], [4], [4'], [4, 4']]) = 4
//     pick = (2^count[1] - 1) * (1 + skip + pick)
//          = len([[1]]) * len([[], [2], [4], [4'], [4, 4']])
//          = len([[1], [1, 2], [1, 4], [1, 4'], [1, 4, 4']]) = 5
//
// So, ans = skip + pick = 9

class Solution {
  public int beautifulSubsets(int[] nums, int k) {
    final int kMax = 1000;
    int[] count = new int[kMax + 1];
    Map<Integer, Set<Integer>> modToSubset = new HashMap<>();

    for (final int num : nums) {
      ++count[num];
      modToSubset.putIfAbsent(num % k, new TreeSet<>());
      modToSubset.get(num % k).add(num);
    }

    int prevNum = -k;
    int skip = 0;
    int pick = 0;

    for (Set<Integer> subset : modToSubset.values())
      for (final int num : subset) {
        final int nonEmptyCount = (int) Math.pow(2, count[num]) - 1;
        final int cacheSkip = skip;
        skip += pick;
        pick = nonEmptyCount * (1 + cacheSkip + (num - prevNum == k ? 0 : pick));
        prevNum = num;
      }

    return skip + pick;
  }
}
// code provided by PROGIEZ

2597. The Number of Beautiful Subsets LeetCode Solution in Python

# e.g. nums = [2, 3, 4, 4], k = 2
#
# subset[0] = [2, 4, 4']
# subset[1] = [1]
# count = {2: 1, 4: 2, 1: 1}
#
# Initially, skip = len([]) = 0, pick = len([]) = 0
#
# * For values in subset[0]:
#   After 2:
#     skip = skip + pick = len([]) = 0
#     pick = (2^count[2] - 1) * (1 + skip + pick)
#          = len([[2]]) * len([[]])
#          = len([[2]]) = 1
#   After 4:
#     skip = skip + pick = len([[2]]) = 1
#     pick = (2^count[4] - 1) * (1 + skip)
#          = len([[4], [4'], [4, 4']]) * len([[]])
#          = len([[4], [4'], [4, 4']]) = 3
#
# * For values in subset[1]:
#   After 1:
#     skip = skip + pick
#          = len([[2], [4], [4'], [4, 4']]) = 4
#     pick = (2^count[1] - 1) * (1 + skip + pick)
#          = len([[1]]) * len([[], [2], [4], [4'], [4, 4']])
#          = len([[1], [1, 2], [1, 4], [1, 4'], [1, 4, 4']]) = 5
#
# So, ans = skip + pick = 9

class Solution:
  def beautifulSubsets(self, nums: list[int], k: int) -> int:
    count = collections.Counter(nums)
    modToSubset = collections.defaultdict(set)

    for num in nums:
      modToSubset[num % k].add(num)

    prevNum = -k
    skip = 0
    pick = 0

    for subset in modToSubset.values():
      for num in sorted(subset):
        nonEmptyCount = 2**count[num] - 1
        skip, pick = (skip + pick,
                      nonEmptyCount *
                      (1 + skip + (0 if num - prevNum == k else pick)))
        prevNum = num

    return skip + pick
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.