Scale Engineer

The Number of Beautiful Subsets

Med
#2377Time: O(2^N * N^2), where N is the length of `nums`. There are `2^N` subsets. For each subset of size `s`, we take O(N) to build it and O(s^2) (at most O(N^2)) to check if it's beautiful.Space: O(N), where N is the length of `nums`. This space is used to store the current subset being checked.1 company
Patterns
MathDynamic ProgrammingBacktrackingCombinatorics
Algorithms
Sorting
Data structures
ArrayHash Table
Companies
Infosys

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible non-empty subset of the given array nums. For each subset, a check is performed to see if it meets the 'beautiful' criteria, which means no two elements within the subset have an absolute difference equal to k. A counter is maintained for all subsets that satisfy this condition.

Algorithm

  1. Initialize a counter beautifulSubsetsCount to 0.
  2. Determine the size of the input array, n.
  3. Iterate through all possible non-empty subsets using a bitmask. Loop an integer i from 1 to (1 << n) - 1.
  4. For each i, construct the corresponding subset:
    • Create an empty list subset.
    • Iterate from j = 0 to n - 1. If the j-th bit of i is set, add nums[j] to subset.
  5. Check if the generated subset is beautiful:
    • Assume the subset is beautiful (isBeautiful = true).
    • Iterate through all pairs of elements (x, y) in the subset.
    • If abs(x - y) == k, set isBeautiful = false and break the inner loops.
  6. If isBeautiful is still true after checking all pairs, increment beautifulSubsetsCount.
  7. After iterating through all bitmasks, return beautifulSubsetsCount.

Walkthrough

The most straightforward way to solve this problem is to generate all 2^n - 1 non-empty subsets of nums. A common technique for this is using bit manipulation, where each integer from 1 to 2^n - 1 represents a unique subset. The j-th bit of the integer corresponds to the j-th element of the nums array. If the bit is 1, the element is included in the subset.

Once a subset is formed, we must validate if it's beautiful. This is done by comparing every pair of elements in the subset. If we find any pair (a, b) such that abs(a - b) == k, the subset is not beautiful, and we can stop checking it and move to the next subset. If all pairs are checked and the condition is never met, we increment our count of beautiful subsets.

import java.util.ArrayList;import java.util.List; class Solution {    public int beautifulSubsets(int[] nums, int k) {        int n = nums.length;        int beautifulSubsetsCount = 0;         for (int i = 1; i < (1 << n); i++) {            List<Integer> subset = new ArrayList<>();            for (int j = 0; j < n; j++) {                if ((i >> j & 1) == 1) {                    subset.add(nums[j]);                }            }             if (isBeautiful(subset, k)) {                beautifulSubsetsCount++;            }        }         return beautifulSubsetsCount;    }     private boolean isBeautiful(List<Integer> subset, int k) {        int size = subset.size();        for (int i = 0; i < size; i++) {            for (int j = i + 1; j < size; j++) {                if (Math.abs(subset.get(i) - subset.get(j)) == k) {                    return false;                }            }        }        return true;    }}

Complexity

Time

O(2^N * N^2), where N is the length of `nums`. There are `2^N` subsets. For each subset of size `s`, we take O(N) to build it and O(s^2) (at most O(N^2)) to check if it's beautiful.

Space

O(N), where N is the length of `nums`. This space is used to store the current subset being checked.

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Works correctly for small input sizes.

Cons

  • Highly inefficient due to its time complexity.

  • Will likely result in a 'Time Limit Exceeded' error for larger constraints (e.g., N > 16).

Solutions

public class Solution {    public int BeautifulSubsets(int[] nums, int k) {        int ans = -1;        int[] cnt = new int[1010];        int n = nums.Length;        void Dfs(int i) {            if (i >= n) {                ans++;                return;            }            Dfs(i + 1);            bool ok1 = nums[i] + k >= 1010 || cnt[nums[i] + k] == 0;            bool ok2 = nums[i] - k < 0 || cnt[nums[i] - k] == 0;            if (ok1 && ok2) {                cnt[nums[i]]++;                Dfs(i + 1);                cnt[nums[i]]--;            }        }        Dfs(0);        return ans;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem