The Number of Beautiful Subsets - Solution & Explanation
Problem Statement
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 <= 1000
Approach Overview
Problem 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 1: Approach 1: Iterative Solution using a Stack
This approach involves using an explicit stack to simulate recursion. We push tasks onto the stack as we go, allowing us to backtrack and manage different states or subproblems efficiently.
This C solution uses an iterative approach with a stack to keep track of tasks.
Complexity
Time Complexity: O(n), Space Complexity: O(n)
Approach 2: Approach 2: Recursive Solution with Memoization
This approach is based on solving subproblems recursively, caching the results of completed subproblems, to avoid redundant calculations, greatly improving efficiency.
This C solution uses recursion with memoization to cache results of subproblems.
Complexity
Time Complexity: O(n), Space Complexity: O(n)
Approach 3: Counting + Backtracking
We use a hash table or array cnt to record the currently selected numbers and their counts, and use ans to record the number of beautiful subsets. Initially, ans = -1 to exclude the empty set.
For each number x in the array nums, we have two choices:
- Do not select
x, and directly recurse to the next number; - Select
x, and check ifx + kandx - khave already appeared incnt. If neither has appeared, we can selectx. In this case, we increment the count ofxby one, recurse to the next number, and then decrement the count ofxby one.
Finally, we return ans.
The time complexity is O(2^n), and the space complexity is O(n). Where n is the length of the array nums.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Solution using a Stack | Time Complexity: O(n), Space Complexity: O(n) |
| Approach 2: Recursive Solution with Memoization | Time Complexity: O(n), Space Complexity: O(n) |
| Counting + Backtracking | — |
Detailed Complexity Analysis
| 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 |
Video Solution
The Number of Beautiful Subsets - Leetcode 2597 - Python • NeetCodeIO • 13,663 views views
Watch 9 more video solutions →Frequently Asked Questions
Is The Number of Beautiful Subsets easy or hard?
The Number of Beautiful Subsets Python/Java solution
How to solve The Number of Beautiful Subsets in O(n)?
What is the best approach for The Number of Beautiful Subsets?
Is The Number of Beautiful Subsets asked at Google/Amazon/Meta?
What data structure is used in The Number of Beautiful Subsets?
What is the time complexity of The Number of Beautiful Subsets?
Ready to solve this problem?
Practice The Number of Beautiful Subsets with our built-in code editor and test cases.
Practice on FleetCode