LeetCode 2597 - The Number of Beautiful Subsets

LeetCode Problem 2597

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Dynamic Programming, Backtracking, Sorting, Combinatorics

Solution

Problem Understanding

The problem asks us to count how many non-empty subsets of the array nums are considered "beautiful".

A subset is beautiful if there are no two numbers inside the subset whose absolute difference equals k.

For example, if k = 2, then the subset cannot contain both 2 and 4, because:

$$|2 - 4| = 2$$

Similarly, it cannot contain both 4 and 6.

The input consists of:

• An integer array nums
• A positive integer k

The output should be the total number of non-empty subsets that satisfy the condition.

An important detail is that subsets are determined by indices, not only by values. If the array contains duplicate values, choosing different copies counts as different subsets.

The constraints are extremely important:

• nums.length <= 18
• Each value is at most 1000

Since the array length is only 18, the total number of subsets is:

$$2^{18} = 262144$$

This is small enough that exponential solutions are acceptable. That observation strongly suggests that backtracking or subset enumeration is intended.

Several edge cases are important:

• Arrays with duplicate numbers
• Cases where many pairs differ by k
• Cases where no pair differs by k
• Arrays of length 1
• Situations where k is larger than any possible difference

For example:

• nums = [1,1,1], k = 2

• Every subset is beautiful because no difference can equal 2.

• nums = [1,3,5], k = 2

• Many combinations become invalid because adjacent values differ by 2.

• nums = [1]

• The single non-empty subset is valid.

The problem guarantees:

• All numbers are positive
• k is positive
• The array size is small enough for exponential exploration

This means we can safely use recursive subset generation without risking time limit issues.

Approaches

Brute Force Approach

The most direct solution is to generate every possible subset and then check whether it is beautiful.

There are 2^n subsets. For each subset, we can compare every pair of elements and verify that no pair has absolute difference k.

For a subset of size m, checking validity costs O(m^2).

In the worst case:

• There are 2^n subsets
• Each subset may contain up to n elements
• Validity checking costs O(n^2)

So the total complexity becomes:

$$O(2^n \cdot n^2)$$

This works for n <= 18, but it performs unnecessary repeated work because many invalid subsets are explored completely before rejection.

Optimal Approach

The key observation is that we do not need to generate an entire subset before checking validity.

Instead, while building the subset incrementally, we can immediately reject choices that violate the condition.

Suppose we are considering whether to add a value x.

The subset becomes invalid only if it already contains:

$$x - k$$

or

$$x + k$$

Because the condition is specifically about absolute difference equal to k.

We can maintain a frequency map of the numbers currently included in the subset.

Before adding x, we simply check whether x - k already exists in the subset.

Why is checking only x - k sufficient?

Because we process elements one by one. If x + k was previously inserted, then when that larger number was added, it would already have checked against x. One directional checking is enough during recursive construction.

This allows pruning invalid branches immediately.

The resulting algorithm is a classic backtracking solution with efficient validity checking using a hash map.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n^2)	O(n)	Generate every subset, then validate separately
Optimal	O(2^n)	O(n)	Backtracking with pruning using a frequency map

Algorithm Walkthrough

Step 1: Initialize a Frequency Map

We maintain a hash map called frequency.

This map stores how many times each number currently exists in the subset being built.

For example:

Subset: [2, 6]
frequency = {
    2: 1,
    6: 1
}

The map allows constant-time checks for conflicts.

Step 2: Define a Recursive Backtracking Function

The recursive function processes elements one by one.

At index i, we have two choices:

1. Skip nums[i]
2. Include nums[i], if it does not violate the beautiful condition

This naturally forms a binary decision tree.

Step 3: Base Case

If we reach the end of the array:

if index == len(nums):

then we have constructed one valid subset.

We return 1.

This counts the current subset configuration.

Step 4: Explore the "Skip" Choice

We always have the option to ignore the current number.

So we recursively continue:

count = backtrack(index + 1)

Step 5: Check Whether Inclusion is Safe

Suppose the current value is:

value = nums[index]

The subset becomes invalid only if:

value - k

already exists in the subset.

So we check:

if frequency[value - k] == 0:

If no conflict exists, we may safely include the value.

Step 6: Include the Value

We update the frequency map:

frequency[value] += 1

Then recursively continue:

count += backtrack(index + 1)

Step 7: Backtrack

After recursion finishes, we must restore the previous state.

So we remove the value:

frequency[value] -= 1

This ensures sibling recursive branches start with the correct subset state.

Step 8: Remove the Empty Subset

The recursion counts all subsets, including the empty subset.

The problem asks only for non-empty subsets.

So the final answer is:

backtrack(0) - 1

Why it works

At every recursive step, the algorithm maintains the invariant that the current subset is beautiful.

A new value is added only if it does not create a forbidden difference of k.

Since every subset is generated exactly once through include/exclude decisions, and invalid states are never explored, the algorithm counts precisely all beautiful subsets.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        frequency = defaultdict(int)
        n = len(nums)

        def backtrack(index: int) -> int:
            if index == n:
                return 1

            count = backtrack(index + 1)

            value = nums[index]

            if frequency[value - k] == 0:
                frequency[value] += 1
                count += backtrack(index + 1)
                frequency[value] -= 1

            return count

        return backtrack(0) - 1

The implementation closely follows the recursive decision process described earlier.

The frequency hash map tracks which values are currently inside the subset. This enables constant-time conflict detection.

The recursive function backtrack(index) returns the number of beautiful subsets that can be formed starting from the current index.

For every element, the algorithm first explores the branch where the element is skipped. Then it checks whether including the element would violate the beautiful condition.

If inclusion is safe, the value is added to the frequency map, recursion continues, and then the value is removed during backtracking.

Finally, the empty subset is excluded from the result by subtracting one.

Go Solution

func beautifulSubsets(nums []int, k int) int {
	frequency := make(map[int]int)
	n := len(nums)

	var backtrack func(int) int

	backtrack = func(index int) int {
		if index == n {
			return 1
		}

		count := backtrack(index + 1)

		value := nums[index]

		if frequency[value-k] == 0 {
			frequency[value]++

			count += backtrack(index + 1)

			frequency[value]--
		}

		return count
	}

	return backtrack(0) - 1
}

The Go implementation mirrors the Python logic very closely.

Go uses a map[int]int instead of Python's defaultdict(int). Missing keys automatically return zero values, so explicit existence checks are unnecessary.

The recursive function is declared as a closure using:

var backtrack func(int) int

Since Go integers are 64-bit on most modern systems and the answer is bounded by 2^18, integer overflow is not a concern.

Worked Examples

Example 1

Input:

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

We recursively explore all subsets.

Step	Current Subset	Valid?	Counted?
[]	Empty subset	Yes	No
[2]	Valid	Yes	Yes
[4]	Valid	Yes	Yes
[6]	Valid	Yes	Yes
[2,4]	Invalid, difference is 2	No	No
[2,6]	Valid	Yes	Yes
[4,6]	Invalid, difference is 2	No	No
[2,4,6]	Invalid	No	No

Final answer:

4

Detailed Recursive Trace

Index	Value	Current Frequency	Action
0	2	{}	Skip
1	4	{}	Skip
2	6	{}	Skip
3	End	{}	Count 1
2	6	{}	Include 6
3	End	{6:1}	Count 1
1	4	{}	Include 4
2	6	{4:1}	Cannot include
0	2	{}	Include 2
1	4	{2:1}	Cannot include
2	6	{2:1}	Include 6

Total counted subsets:

[], [6], [4], [2], [2,6]

Subtract empty subset:

5 - 1 = 4

Example 2

Input:

nums = [1]
k = 1

Possible subsets:

Subset	Valid?
[]	Yes
[1]	Yes

Total valid subsets:

2

Exclude empty subset:

2 - 1 = 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n)	Each element has two choices, include or exclude
Space	O(n)	Recursion depth and frequency map storage

The recursion explores a binary decision tree. Since every element can either be included or excluded, the total number of recursive states is proportional to 2^n.

The frequency map stores at most n elements at a time, and the recursion stack depth is also at most n.

Because n <= 18, this exponential solution is efficient enough.

Test Cases

sol = Solution()

assert sol.beautifulSubsets([2, 4, 6], 2) == 4  # provided example
assert sol.beautifulSubsets([1], 1) == 1  # single element

assert sol.beautifulSubsets([1, 2, 3], 1) == 4  # adjacent conflicts
assert sol.beautifulSubsets([1, 1, 1], 2) == 7  # duplicates with no conflicts
assert sol.beautifulSubsets([1, 3, 5], 2) == 4  # chain conflicts

assert sol.beautifulSubsets([10, 20, 30], 15) == 7  # no conflicts at all
assert sol.beautifulSubsets([4, 4, 4], 0) == 7  # duplicates, though k is positive in constraints

assert sol.beautifulSubsets([1, 2, 4, 6], 2) == 8  # multiple valid combinations
assert sol.beautifulSubsets([2, 2, 4], 2) == 4  # duplicates interacting with conflicts

assert sol.beautifulSubsets([1000], 1000) == 1  # maximum value edge case

Test	Why
[2,4,6], k=2	Basic example with conflicts
[1], k=1	Smallest input
[1,2,3], k=1	Consecutive numbers create many invalid subsets
[1,1,1], k=2	Duplicates without conflicts
[1,3,5], k=2	Conflict chain structure
[10,20,30], k=15	No conflicts, all subsets valid
[4,4,4], k=0	Duplicate edge case outside official constraints
[1,2,4,6], k=2	Multiple interacting conflicts
[2,2,4], k=2	Duplicates combined with forbidden difference
[1000], k=1000	Maximum value boundary

Edge Cases

Duplicate Numbers

Arrays containing duplicates are easy to mishandle because subsets are index-based, not value-based.

For example:

nums = [1,1,1]
k = 2

All non-empty subsets are valid because no pair differs by 2.

A buggy implementation might accidentally treat duplicates as identical and undercount subsets.

This implementation handles duplicates correctly because recursion processes indices independently, while the frequency map tracks counts rather than unique existence only.

No Valid Pair Restrictions

Consider:

nums = [10,20,30]
k = 100

No two numbers differ by 100.

Therefore every non-empty subset is beautiful.

The algorithm correctly counts all:

$$2^n - 1$$

possible non-empty subsets because no inclusion check ever fails.

Long Conflict Chains

Consider:

nums = [1,3,5,7]
k = 2

Each number conflicts with neighboring values.

Naive solutions may accidentally allow invalid combinations like [1,3].

The frequency-map validation prevents this immediately during construction. Invalid branches are pruned before deeper recursion occurs.

Empty Subset Handling

The recursion naturally counts the empty subset because repeatedly choosing "skip" reaches the base case.

However, the problem explicitly asks for non-empty subsets only.

The implementation handles this carefully by subtracting one from the final count.