Watch 10 video solutions for The Number of Beautiful Subsets, a medium level problem involving Array, Hash Table, Math. This walkthrough by NeetCodeIO has 13,490 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 201 <= nums[i], k <= 1000Problem Overview: You are given an integer array nums and an integer k. A subset is considered beautiful if no two elements in the subset have an absolute difference equal to k. The task is to count all non-empty beautiful subsets.
Approach 1: Iterative Solution using a Stack (Time: O(2^n), Space: O(n))
This approach simulates the classic subset generation process using an explicit stack instead of recursion. First sort the array so conflicting values (difference k) are easier to detect. As you iterate through elements, push states representing partial subsets onto the stack. A hash table tracks which numbers are currently in the subset; before adding a value x, check whether x - k or x + k already exists in the current selection. If neither exists, the subset remains valid and the state is pushed for further expansion. Each valid state contributes to the count. This method explicitly explores the subset decision tree while keeping the constraint check O(1).
Approach 2: Recursive Solution with Memoization (Time: O(2^n), Space: O(n))
This method uses backtracking to explore all inclusion/exclusion choices. After sorting the array, recursively process each index. At each step you have two options: skip the current number or include it if doing so does not create a difference of k with any selected element. A frequency map tracks chosen numbers so you can check conflicts in constant time. Memoization can cache results based on the current index and the frequency state representation to avoid recomputing identical branches. This keeps the recursion manageable even when many values repeat.
Recommended for interviews: The recursive backtracking approach with a hash map is the most commonly expected solution. It clearly demonstrates how you enforce constraints while generating subsets. Interviewers often want to see the reasoning behind pruning invalid branches early. The iterative stack version is conceptually similar but useful when you want to avoid recursion or explicitly manage the search stack.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Stack-Based Subset Generation | O(2^n) | O(n) | When you want an explicit stack instead of recursion and full control over state expansion |
| Recursive Backtracking with Memoization | O(2^n) | O(n) | General interview solution that cleanly prunes invalid subsets using a hash map |