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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

The Number of Beautiful Subsets

Difficulty: Medium

Problem 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.

Key Insights

  • A subset is considered beautiful if it does not include pairs of elements whose absolute difference is k.
  • The constraints allow for a maximum of 18 elements in nums, which suggests that a combinatorial approach (like backtracking or bit manipulation) could be feasible.
  • Each element in nums can either be included in a subset or not, leading to a total of 2^n possible subsets.
  • We need to check each subset to ensure it meets the beautiful condition.

Space and Time Complexity

Time Complexity: O(2^n * n), where n is the number of elements in the array. This accounts for generating all subsets and checking each subset for the beautiful condition.

Space Complexity: O(n), which is used for storing the current subset during the backtracking process.

Solution

To solve the problem, we can use a backtracking approach to generate all possible subsets of the given array nums. For each subset generated, we will check if it satisfies the condition of being beautiful by ensuring that no two elements in the subset have an absolute difference of k.

We can utilize a set to track the elements included in the current subset and validate the beautiful condition efficiently.

Code Solutions

def beautifulSubsets(nums, k):
    def backtrack(start, current_subset):
        if start == len(nums):
            return 1 if current_subset else 0  # Count the non-empty subset
        count = 0
        # Exclude the current element
        count += backtrack(start + 1, current_subset)
        
        # Include the current element
        if all(abs(nums[start] - x) != k for x in current_subset):
            current_subset.add(nums[start])
            count += backtrack(start + 1, current_subset)
            current_subset.remove(nums[start])
        
        return count
    
    return backtrack(0, set())

# Example usage
print(beautifulSubsets([2, 4, 6], 2))  # Output: 4
print(beautifulSubsets([1], 1))        # Output: 1
← Back to All Questions