2597. The Number of Beautiful Subsets

MediumArrayDynamic ProgrammingBacktracking
Leetcode Link

Problem Description

This problem involves analyzing a collection of positive integers, provided within an array nums, along with a given positive integer k. The objective is to determine the count of "beautiful" subsets that you can derive from the original array. A subset is considered beautiful if none of its element pairs have an absolute difference equal to k.

In more simple terms, you are tasked with finding every possible combination of numbers from the given array such that no two numbers in any combination are k units apart from each other. Remember that a subset means any selection of elements from nums, including possibly none - meaning, the full array nums itself can be a subset as long as no two of its elements have an absolute difference of k. Each subset is unique if it's derived from a unique set of indices chosen for deletion from nums.

Importantly, because subsets can vary in size from just one element up to the full length of the original array, there are potentially many such subsets, and you're required to report their count.

Intuition

The solution approach leverages recursive backtracking, which is a well-suited technique for problems involving combinatorial computations such as this one. The primary idea is to iterate through the array and make a decision at each step whether to include or exclude the current number from a subset we're building. We adapt this common pattern slightly by keeping track of the numbers we've included so far and their counts in a counter structure, which is essential for applying our beautiful subset rule regarding the absolute difference.

When we include a number in a subset, we check the counter to ensure that including it would not violate the condition of having an absolute difference of k with any other included numbers. If including it is valid, we add it to our counter, recurse to consider further numbers, and upon returning from the recursion, we backtrack by reverting the change to our counter to ensure it's ready for the next iteration.

In tackling the problem with backtracking, we systematically explore all subsets, validating and counting all the beautiful ones. The technique is exhaustive and ensures that we consider each possible subset.

The process begins with an answer counter set to -1 to exclude the empty set from the solution, as specified by the problem statement, before starting our Depth-First Search (DFS) traversal. Through this traversal, we either pass over a number or include it, depending on whether it meets the beautiful subset condition. By the end, we'll have traversed all possibilities and accumulated the total count of valid subsets in our answer variable.

Learn more about Dynamic Programming and Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

In a binary min heap, the minimum element can be found in:

Solution Approach

The solution to this problem utilizes recursive backtracking alongside a counting mechanism, which together form a powerful approach to generate and validate the subsets of nums.

The centerpiece of this implementation is the dfs function, which stands for Depth-First Search. This recursive function is what allows us to consider every subset of nums for its beauty according to the provided condition related to k. The base case of this recursion occurs when all elements have been considered, at which point one valid subset path has been completed and the ans is incremented by one.

The ans variable is used to accumulate the number of beautiful subsets found. It is initialized to -1 because the empty set is not counted, according to the problem statement.

The data structure cnt is a Counter from the Python collections library and it serves to maintain the count of the numbers included in the current subset being evaluated. The Counter provides us a fast way to check the existence and count of elements.

In each recursive call, there are two choices:

  1. Exclude the current number i from the subset.

    • This doesn't impact the cnt, hence we simply call dfs(i + 1) and move on to the next number without changing the state.

  2. Include the current number i in the subset.

    • Before we can make this choice, a validation check decides if the number can be included by ensuring that neither nums[i] + k nor nums[i] - k is currently in the subset (dictated by seeing if they are not in the Counter).
    • If the number passes validation, it's count in cnt is incremented by 1 and dfs(i + 1) is called to consider the next number.
    • After the recursive call returns, we backtrack by decrementing the count of nums[i] in cnt to undo the last choice. This step is crucial and ensures that the state is maintained correctly for further exploration of subsets.

It is worth noticing that the decision to increment ans unconditionally with every completed and returned recursion path subtly captures all non-empty subsets' combinations.

Finally, the function beautifulSubsets returns the accumulated count in ans.

It must be mentioned that this recursive and backtracking algorithm is exhaustive, which means that it operates well for smaller inputs but may suffer from performance issues with large inputs due to the exponential number of possible subsets. Nonetheless, this brute-force approach cleverly uses counting to avoid illegal subsets and ensures a comprehensive search through the subset space.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Example Walkthrough

Let us consider a small example to illustrate the solution approach. Suppose we have an array nums = [1, 3, 5] and k = 2.

We want to count all the beautiful subsets of nums where no two numbers have an absolute difference equal to k. Here, we will be looking for subsets where no two numbers are exactly 2 units apart.

Initially, our ans is set to -1 to exclude the empty set. We now perform DFS to explore all subsets.

  1. Start with an empty subset, and empty counter cnt.

  2. For the first element 1, we have two choices:

    • Exclude 1: Recursively continue with the next element of nums.
    • Include 1: Update cnt by incrementing the count of 1. Now, cnt = Counter({1: 1}). Recursively continue with the next element, ensuring not to include 3 in any subset because 3 - 1 = k.

  3. For the next element, 3, following the same choices:

    • Exclude 3: No change in cnt. Continue to the next element.
    • As we have 1 in our cnt, including 3 is not valid because abs(3 - 1) = k. We cannot proceed with this option.

  4. Next, for the element 5, we again have two choices:

    • Exclude 5: If we previously excluded 3, a subset [1] is counted, ans = ans + 1. We will proceed to backtrack and consider the other options.
    • Include 5: This is valid if 3 was excluded. Now we have a subset [1, 5], and cnt is updated to Counter({1: 1, 5: 1}), ans = ans + 1. We backtrack after this since there are no more elements to consider.

By the end, we will have considered all possible subsets, and our ans variable will contain the count of all non-empty beautiful subsets. For this example, the subsets we count are [1], [3], [5], [1, 5]. Therefore, the returned ans is 3 (since we started with -1).

Now imagine we had not started with ans = -1, we would have also implicitly counted the empty subset, resulting in ans being 4.

This walkthrough demonstrates how we utilize recursive backtracking to manage state and systematically explore all possible subsets, validating against the given condition and counting those that are beautiful.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def beautifulSubsets(self, nums: List[int], k: int) -> int:
5        # Helper depth-first search function to generate subsets and count the beautiful ones.
6        def depth_first_search(index: int) -> None:
7            nonlocal beautiful_count # This allows us to modify a variable outside of the nested function's scope.
8            # Base case: check if we have considered all numbers.
9            if index >= len(nums):
10                beautiful_count += 1 # Found a beautiful subset.
11                return
12          
13            # Recursive case 1: Skip the current number and move to the next.
14            depth_first_search(index + 1)
15          
16            # Recursive case 2: Include the current number if it can form a beautiful subset.
17            if count[nums[index] + k] == 0 and count[nums[index] - k] == 0:
18                count[nums[index]] += 1 # Include the current number in the count.
19                depth_first_search(index + 1) # Move to the next number.
20                count[nums[index]] -= 1 # Backtrack by removing the current number from the count.
21
22        # Initialize the answer to -1 to account for the empty subset which is not considered beautiful.
23        beautiful_count = -1
24        count = Counter() # Counter to track the occurrences of numbers in the current subset.
25      
26        # Begin the depth-first search with the first number in the list.
27        depth_first_search(0)
28      
29        return beautiful_count # Return the final count of beautiful subsets.
30
31# Example usage:
32# solution = Solution()
33# result = solution.beautifulSubsets([1,2,3,4], 1)
34# print(result)  # Output will depend on the input list and the value of k
35
1class Solution {
2    private int[] nums; // array of given numbers
3    private int[] count = new int[1010]; // frequency array to keep track of elements in the subset
4    private int totalBeautifulSubsets = 0; // total count of beautiful subsets found
5    private int k; // the difference value used to determine beauty of a subset
6
7    // Method to find the count of beautiful subsets from a given array with respect to 'k'
8    public int beautifulSubsets(int[] nums, int k) {
9        this.k = k;
10        this.nums = nums;
11        findBeautifulSubsets(0); // start the DFS with the first element in the array
12        return totalBeautifulSubsets;
13    }
14
15    // Recursive method to perform DFS and find all subsets that are considered beautiful
16    private void findBeautifulSubsets(int index) {
17        // Base case: if we've considered all elements in 'nums'
18        if (index >= nums.length) {
19            totalBeautifulSubsets++; // we've formed a subset, increment the beautiful subsets count
20            return;
21        }
22        // Option 1: Exclude the current element and explore further subsets
23        findBeautifulSubsets(index + 1);
24
25        // Check if including nums[index] in the subset still keeps it beautiful
26        boolean isBeautifulWithNext = nums[index] + k >= count.length || count[nums[index] + k] == 0;
27        boolean isBeautifulWithPrevious = nums[index] - k < 0 || count[nums[index] - k] == 0;
28
29        // If both checks pass, the subset remains beautiful with the inclusion of nums[index]
30        if (isBeautifulWithNext && isBeautifulWithPrevious) {
31            count[nums[index]]++; // include the current element by incrementing its frequency
32            findBeautifulSubsets(index + 1); // explore further subsets including this element
33            count[nums[index]]--; // backtrack and exclude the current element
34        }
35    }
36}
37
1class Solution {
2public:
3    int beautifulSubsets(vector<int>& nums, int k) {
4        int countBeautifulSubsets = -1; // Initialize the counter for beautiful subsets to -1.
5        int countNums[1010]{}; // Array to keep track of the frequency of each number.
6        int size = nums.size(); // Store the size of the input vector 'nums'.
7
8        // Define a recursive lambda function to perform depth-first search for beautiful subsets.
9        function<void(int)> dfs = [&](int index) {
10            if (index >= size) { // Base case: If the end of the array is reached,
11                ++countBeautifulSubsets; // increment the count of beautiful subsets.
12                return; // Exit the current recursive call.
13            }
14            dfs(index + 1); // Recursive call to continue without including the current number.
15          
16            // Check if the number is considered beautiful in the context of the subset being formed.
17            bool isBeautifulIncrement = nums[index] + k >= 1010 || countNums[nums[index] + k] == 0;
18            bool isBeautifulDecrement = nums[index] - k < 0 || countNums[nums[index] - k] == 0;
19
20            // If both conditions are true, the number can be included in the subset.
21            if (isBeautifulIncrement && isBeautifulDecrement) {
22                ++countNums[nums[index]]; // Increment the count for the current number.
23                dfs(index + 1); // Recursive call to continue with the current number included.
24                --countNums[nums[index]]; // Backtrack: Decrement the count after exploring.
25            }
26        };
27
28        dfs(0); // Start the depth-first search from the first index.
29        return countBeautifulSubsets; // Return the final count of beautiful subsets.
30    }
31};
32
1function beautifulSubsets(nums: number[], k: number): number {
2    let answer: number = -1; // Initialize answer with -1 as the base case.
3    const count: number[] = new Array(1010).fill(0); // Count array with size 1010 to track occurrences.
4    const len: number = nums.length; // Cache the length of nums.
5
6    // Helper function to perform depth-first search.
7    function dfs(index: number) {
8        if (index >= len) {
9            // If the end of the array is reached, increment the answer.
10            answer++;
11            return;
12        }
13
14        // Recursive case: proceed to next element without including current.
15        dfs(index + 1);
16
17        // Check if adding the current element is valid.
18        const isAddableAbove: boolean = nums[index] + k >= 1010 || count[nums[index] + k] === 0;
19        const isAddableBelow: boolean = nums[index] - k < 0 || count[nums[index] - k] === 0;
20
21        // If the current element can be added without breaking the 'beautiful' condition.
22        if (isAddableAbove && isAddableBelow) {
23            count[nums[index]]++; // Increment the count for this number.
24            dfs(index + 1); // Continue to next element with current included.
25            count[nums[index]]--; // Decrement the count after backtracking.
26        }
27    }
28
29    // Start depth-first search from index 0.
30    dfs(0);
31    return answer; // Return the total count of 'beautiful' subsets.
32}
33
34// Usage.
35const nums = [1, 2, 3]; // Example array.
36const k = 1; // Example difference.
37console.log(beautifulSubsets(nums, k)); // Call the function with example inputs and log the result.
38
Not Sure What to Study? Take the 2-min Quiz：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Time and Space Complexity

Time Complexity

The time complexity of the code is O(2^n) where n is the length of the array nums. This is because in the worst case, for every element in the array, the dfs function is called twice: once when the element is included in the subset and once when the element is excluded. This results in a binary tree with 2^n leaves, representing all the possible subsets.

Space Complexity

The space complexity of the code is O(n) due to the recursion depth and the additional space used by the cnt counter. In the worst case, the depth of the recursion call stack will be n when we keep including elements until we reach the end of the array. Moreover, cnt is a counter that keeps track of how many times an element appears in the current subset which takes at most O(n) space if all elements are distinct.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫