NeetCode #509LC-2597MediumBacktracking
← Back to All Problems#509 · #2597 · The Number of Beautiful Subsets(美丽子集的数目)
📌 Problem Statement & Constraints
You are given an array
nums of positive integers and a positive integer k. A subset is beautiful if it contains no two elements whose absolute difference is k. Return the number of non-empty beautiful subsets. Constraints: 1 <= nums.length <= 20, 1 <= nums[i], k <= 1000.💡 Core Algorithmic Approaches
- Backtrack over the indices with an include/exclude decision at each step.
- Including
nums[i]is allowed only when neithernums[i] - knornums[i] + kis already in the subset. - A frequency map of the current subset makes that check O(1).
- Count each inclusion, since every non-empty subset corresponds to exactly one set of include decisions.
💻 Benchmark Python3 Implementation
class Solution:
def beautifulSubsets(self, nums: List[int], k: int) -> int:
from collections import Counter
cnt = Counter() # values in the current subset
self.res = 0
def dfs(i: int) -> None:
if i == len(nums):
return
v = nums[i]
# include nums[i] if no forbidden partner is present
if cnt[v - k] == 0 and cnt[v + k] == 0:
cnt[v] += 1
self.res += 1 # this subset is non-empty and valid
dfs(i + 1)
cnt[v] -= 1
dfs(i + 1) # exclude nums[i]
dfs(0)
return self.res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(2^n): each subset is visited once with O(1) work.
💾 Space Complexity
O(n) for the recursion depth and the counter.
⚠️ Interview Pitfalls & Follow-ups
- Checking only
v - kor onlyv + k: both directions matter, since the subset may contain either. - Counting subsets at the leaves only: each inclusion event corresponds to one complete subset, so counting there is correct and avoids a leaf-level enumeration.
- Forgetting to decrement the counter on backtrack: later branches would see phantom values.
- Using an array indexed by value: values reach 1000 so it works, but the counter adapts to any range.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.