The Number of Beautiful Subsets

medium backtracking subsets pruning

Problem

Given an array nums of positive integers and a positive integer k, a subset is beautiful if it contains no two integers whose absolute difference equals k. Return the number of non-empty beautiful subsets of nums.

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

Output4

The beautiful subsets are [2], [4], [6] and [2,6]. Subsets like [2,4] or [4,6] are excluded because their elements differ by exactly 2.

Inputnums = [1], k = 1

Output1

The only non-empty subset [1] is beautiful.

nums (comma-separated)

def beautifulSubsets(nums, k):
    nums.sort()
    count = {}
    total = 0
    def dfs(i):
        nonlocal total
        if i == len(nums):
            total += 1
            return
        dfs(i + 1)                       # skip nums[i]
        if count.get(nums[i] - k, 0) == 0:
            count[nums[i]] = count.get(nums[i], 0) + 1
            dfs(i + 1)                   # take nums[i]
            count[nums[i]] -= 1
    dfs(0)
    return total - 1                     # drop empty subset

function beautifulSubsets(nums, k) {
  nums.sort((a, b) => a - b);
  const count = new Map();
  let total = 0;
  function dfs(i) {
    if (i === nums.length) { total++; return; }
    dfs(i + 1);                          // skip nums[i]
    if ((count.get(nums[i] - k) || 0) === 0) {
      count.set(nums[i], (count.get(nums[i]) || 0) + 1);
      dfs(i + 1);                        // take nums[i]
      count.set(nums[i], count.get(nums[i]) - 1);
    }
  }
  dfs(0);
  return total - 1;                      // drop empty subset
}

int total = 0;
public int beautifulSubsets(int[] nums, int k) {
    Arrays.sort(nums);
    Map<Integer, Integer> count = new HashMap<>();
    dfs(nums, k, 0, count);
    return total - 1;                    // drop empty subset
}
void dfs(int[] nums, int k, int i, Map<Integer, Integer> count) {
    if (i == nums.length) { total++; return; }
    dfs(nums, k, i + 1, count);          // skip nums[i]
    if (count.getOrDefault(nums[i] - k, 0) == 0) {
        count.merge(nums[i], 1, Integer::sum);
        dfs(nums, k, i + 1, count);      // take nums[i]
        count.merge(nums[i], -1, Integer::sum);
    }
}

int total = 0;
void dfs(vector<int>& nums, int k, int i, unordered_map<int,int>& count) {
    if (i == (int)nums.size()) { total++; return; }
    dfs(nums, k, i + 1, count);          // skip nums[i]
    if (count[nums[i] - k] == 0) {
        count[nums[i]]++;
        dfs(nums, k, i + 1, count);      // take nums[i]
        count[nums[i]]--;
    }
}
int beautifulSubsets(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    unordered_map<int,int> count;
    dfs(nums, k, 0, count);
    return total - 1;                    // drop empty subset
}

Explanation

Every element is either in a subset or out of it, so the search space is a binary decision tree of depth n. We walk it with backtracking: a recursive function dfs(i) decides what to do with nums[i], then recurses on i + 1.

The only rule is that a beautiful subset may not contain two values differing by exactly k. To enforce it cheaply we keep a count map of how many copies of each value are currently chosen. Before taking nums[i] we check whether nums[i] - k is already present; if it is, adding nums[i] would create a forbidden pair, so we prune that branch.

Sorting first guarantees that for any conflicting pair we only ever need to look back by k (the smaller of the two values was decided earlier), so checking nums[i] - k alone is enough — we never need to look forward at nums[i] + k.

When we take an element we increment its count, recurse, then decrement it on the way back — the classic choose / explore / un-choose pattern that restores state for the sibling branch.

Reaching i == n means we have committed to a full include/exclude assignment, which is one valid subset, so we add 1 to total. The empty subset is counted once among these leaves, so the answer is total - 1.

Time: O(2ⁿ) Space: O(n)