The Number of Beautiful Subsets solution and explanation
Infosys
Google
9 more videos on this problem
The Number of Beautiful Subsets - Leetcode 2597 - PythonNeetCodeIO · 32:34 · 13K views
The Number of Beautiful Subsets | Backtracking | Khaandani Template | Leetcode 2597|codestorywithMIKcodestorywithMIK · 14:27 · 12K views
The Number of Beautiful Subsets leetcode || Dynamic Programming || Backtracking || Leetcode-2597Aryan Mittal · 33:24 · 10K views
2597. The Number of Beautiful Subsets | Weekly Contest 337 | LeetCode 2597Bro Coders · 9:00 · 5K views
Leetcode 2597: The Number of Beautiful SubsetsAlgorithms Casts · 13:39 · 2K views
2597. The Number of Beautiful Subsets | backtracking | leetcode daily challenge | DSA | HindiShashCode · 18:57 · 1K views
Leetcode 2597: The Number of Beautiful Subsets | Backtracking | SubsetsComprehensive Code · 13:40 · 1K views
2597. The Number of Beautiful Subsets (Leetcode Medium)Programming Live with Larry · 11:04 · 1K views
The Number of Beautiful Subsets (LeetCode 2597) (Recursion,Backtracking)CodeWithARB · 37:50 · 866 views
The Number of Beautiful Subsets| Leetcode 2597 | Recursion | C++ | Weekly 337Tech Courses · 10:00 · 567 views
The problem
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.
def iterative_solution(arr):
# Your code logic here
return resultint iterativeSolution(int[] arr) {
// Your code logic here
}int iterativeSolution(std::vector<int>& arr) {
// Your code logic here
}function iterativeSolution(arr) {
// Your code logic here
}int iterativeSolution(int* arr, int n) {
// Your code logic here
}int IterativeSolution(int[] arr) {
// Your code logic here
}This Python solution uses an iterative approach with a stack to keep track of tasks.
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.
def recursive_with_memoization(arr, memo, n):
# Your code logic here
return resultint recursiveWithMemoization(int[] arr, int[] memo, int n) {
// Your code logic here
}int recursiveWithMemoization(std::vector<int>& arr, std::vector<int>& memo) {
// Your code logic here
}function recursiveWithMemoization(arr, memo, n) {
// Your code logic here
}int recursiveWithMemoization(int* arr, int n, int* memo) {
// Your code logic here
}int RecursiveWithMemoization(int[] arr, int[] memo, int n) {
// Your code logic here
}This Python solution uses recursion with memoization to cache results of subproblems.
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.
function beautifulSubsets(nums: number[], k: number): number {
let ans: number = -1;
const cnt: number[] = new Array(1010).fill(0);
const n: number = nums.length;
const dfs = (i: number) => {
if (i >= n) {
++ans;
return;
}
dfs(i + 1);
const ok1: boolean = nums[i] + k >= 1010 || cnt[nums[i] + k] === 0;
const ok2: boolean = 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;
}func beautifulSubsets(nums []int, k int) int {
ans := -1
n := len(nums)
cnt := [1010]int{}
var dfs func(int)
dfs = func(i int) {
if i >= n {
ans++
return
}
dfs(i + 1)
ok1 := nums[i]+k >= len(cnt) || cnt[nums[i]+k] == 0
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
}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 | – |
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 |
Frequently asked questions
Is The Number of Beautiful Subsets easy or hard?
The Number of Beautiful Subsets is classified as Medium difficulty on LeetCode. The main challenge is recognizing that the problem is a constrained subset generation task and implementing pruning efficiently using a hash map or frequency array.
The Number of Beautiful Subsets Python/Java solution
Both Python and Java implementations usually follow the same pattern: sort the array, use recursion to explore include/exclude choices, and maintain a hash map for frequency tracking. When including nums[i], check whether nums[i] - k is already present. If not, add it, recurse, and backtrack afterward.
How to solve The Number of Beautiful Subsets in O(n)?
A true O(n) solution is not possible because the problem requires evaluating combinations of elements. The optimal strategy uses backtracking or subset generation with pruning, which results in O(2^n) time. Sorting and hash lookups help reduce unnecessary branches but do not eliminate the exponential search space.
What is the best approach for The Number of Beautiful Subsets?
The most practical approach is backtracking with a hash map that tracks which numbers are currently included in the subset. Before adding a number x, check whether x - k or x + k already exists. This pruning prevents invalid subsets early and explores only valid combinations. The overall complexity is O(2^n) time with O(n) recursion space.
Is The Number of Beautiful Subsets asked at Google/Amazon/Meta?
Subset generation and constraint-based backtracking problems are common in interviews at companies like Google, Amazon, and Meta. Variants of this question appear in coding interviews where candidates must generate valid subsets while enforcing constraints such as differences or sums.
What data structure is used in The Number of Beautiful Subsets?
The typical solution uses a hash table (or frequency map) to track numbers currently included in the subset. This allows constant-time checks for values that differ by k. Sorting the array and recursion/backtracking are also commonly used to structure the search process.
What is the time complexity of The Number of Beautiful Subsets?
The time complexity is O(2^n) because every element can either be included or excluded when generating subsets. Constraint checks using a hash table take O(1) time, so the dominant cost comes from exploring the subset decision tree. Space complexity is O(n) for recursion depth or stack storage.