#2597

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

The Number of Beautiful Subsets

Count all non-empty subsets of an array where no two numbers have an absolute difference equal to k, using array scanning and hash lookup.

array hash table math dynamic programming backtracking

Problem Statement

Given an array nums of positive integers and a positive integer k, define a subset of nums as beautiful if it does not contain any two integers whose absolute difference is exactly k. Your task is to count all non-empty beautiful subsets in nums.

Return an integer representing the total number of beautiful subsets. For example, if nums = [2,4,6] and k = 2, the beautiful subsets are [2], [4], [6], and [2,6], resulting in an output of 4.

Examples

Example 1

Input: nums = [2,4,6], k = 2

Output: 4

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

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 <= 18
1 <= nums[i], k <= 1000

Solution Approach

Sort and Track Frequency

Sort nums to handle numbers in increasing order, then create a hash table to store the count of each number. This allows efficient checking for conflicts with previously selected numbers while scanning subsets.

Backtracking with Hash Lookup

Use a recursive backtracking function that attempts to include or exclude each number. Before including a number, check the hash table to see if adding it would create a pair with absolute difference k. Skip numbers that violate the beautiful subset condition.

Count Valid Subsets

Every time a valid subset is formed that obeys the k difference rule, increment a counter. Combine results from all recursive branches to return the total number of non-empty beautiful subsets.

Complexity Analysis

Metric	Value
Time	O(n \log n)
Space	O(n)

Sorting the array takes O(n log n). Backtracking explores up to 2^n subsets, but the hash lookup prevents invalid branches early, keeping practical time complexity manageable for n <= 18. Space is O(n) for the hash table and recursion stack.

What Interviewers Usually Probe

Look for use of sorting plus hash table to avoid O(n^2) pair checks.
Check whether subsets are counted without missing any edge cases with difference k.
Verify handling of small arrays and duplicates using the hash table.

Common Pitfalls or Variants

Common pitfalls

Counting subsets without checking the absolute difference k for all pairs.
Failing to handle duplicate numbers, leading to overcounting.
Recursing without pruning invalid branches, causing unnecessary computation.

Follow-up variants

Count beautiful subsets with at most one pair violating the k difference.
Find all beautiful subsets where the difference must not be a multiple of k.
Return the sum of elements in all beautiful subsets instead of the count.

FAQ

What exactly defines a beautiful subset in this problem?

A beautiful subset contains no two numbers whose absolute difference is exactly k. Any subset violating this is excluded from the count.

Why is sorting nums important for solving this problem?

Sorting allows sequential scanning and ensures that checking the hash table for conflicts is efficient, avoiding unnecessary recomputation for all pairs.

Can this approach handle duplicate numbers in nums?

Yes, the hash table tracks counts of each number, ensuring that duplicates are correctly included or skipped to maintain the beautiful subset rule.

What is the recommended pattern for this problem?

Array scanning combined with hash table lookup is the key pattern, allowing efficient subset generation while enforcing the absolute difference constraint.

How does GhostInterview prevent miscounting subsets?

It guides through each recursive branch, checks the hash table for absolute difference conflicts, and accumulates only valid non-empty beautiful subsets.

terminal

Solution

Solution 1: Counting + Backtracking

We use a hash table or array $\textit{cnt}$ to record the currently selected numbers and their counts, and use $\textit{ans}$ to record the number of beautiful subsets. Initially, $\textit{ans} = -1$ to exclude the empty set.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        def dfs(i: int) -> None:
            nonlocal ans
            if i >= len(nums):
                ans += 1
                return
            dfs(i + 1)
            if cnt[nums[i] + k] == 0 and cnt[nums[i] - k] == 0:
                cnt[nums[i]] += 1
                dfs(i + 1)
                cnt[nums[i]] -= 1

        ans = -1
        cnt = Counter()
        dfs(0)
        return ans

Continue Practicing

#2501 longest square streak in an array #2708 maximum strength of a group #2713 maximum strictly increasing cells in a matrix