⚡Flashcard Drill➔
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

  1. Backtrack over the indices with an include/exclude decision at each step.
  2. Including nums[i] is allowed only when neither nums[i] - k nor nums[i] + k is already in the subset.
  3. A frequency map of the current subset makes that check O(1).
  4. 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 - k or only v + 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems