We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The Number of Beautiful Subsets

Number: 2696

Difficulty: Medium

Paid? No

Companies: Meta, Infosys

Problem Description

Given an array of positive integers nums and a positive integer k, count the number of non-empty subsets of nums (where subsets are defined by chosen indices, even if numbers are repeated) which are considered beautiful. A subset is beautiful if it does not contain any two integers whose absolute difference equals k.

Key Insights

  • Since the maximum length of nums is 18, it is feasible to try all 2^n non-empty subsets.
  • When checking a subset, ensure no two elements have a difference equal to k.
  • For each subset, converting the chosen elements into a set (or sorting) enables efficient pair checks.
  • Brute-force bitmask enumeration or depth-first/backtracking can be used, given the small input size.

Space and Time Complexity

Time Complexity: O(2^n * n), where n is the size of nums (n ≤ 18). Space Complexity: O(n) for generating each subset.

Solution

We use bitmask enumeration to evaluate all possible non-empty subsets. For each bitmask:

  1. Generate the subset by selecting elements corresponding to set bits.
  2. Check if the subset is beautiful by ensuring that for every element v in the subset, v+k does not exist (this avoids having any pair with an absolute difference equal to k).
  3. Count the beautiful subsets and return the count.

The trick here is to leverage bit masks to represent subsets and use a set (or sorting) to check conflicts in O(n) time per subset. Given the small constraint (n ≤ 18), the approach is efficient and straightforward.

Code Solutions

# Python Code Solution

class Solution:
    def beautifulSubsets(self, nums, k):
        n = len(nums)
        beautiful_count = 0

        # Enumerate all non-empty subsets using bitmask
        for mask in range(1, 1 << n):
            subset = []
            for i in range(n):
                if mask & (1 << i):
                    subset.append(nums[i])
            # Use a set for efficient lookup
            subset_set = set(subset)
            valid = True
            for num in subset_set:
                # Check if there exists another number with difference k
                if num + k in subset_set:
                    valid = False
                    break
            if valid:
                beautiful_count += 1
        return beautiful_count

# Example usage:
# sol = Solution()
# print(sol.beautifulSubsets([2,4,6], 2))   # Expected output 4
← Back to All Questions