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.
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.
Time Complexity: O(n), Space Complexity: O(n)
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.
Time Complexity: O(n), Space Complexity: O(n)
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:
x, and directly recurse to the next number;x, and check if x + k and x - k have already appeared in cnt. If neither has appeared, we can select x. In this case, we increment the count of x by one, recurse to the next number, and then decrement the count of x by 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.
| 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 | — |
| 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 |
The Number of Beautiful Subsets - Leetcode 2597 - Python • NeetCodeIO • 13,490 views views
Watch 9 more video solutions →Practice The Number of Beautiful Subsets with our built-in code editor and test cases.
Practice on FleetCode