The number of beautiful subsets

Array Hash Table Math Dynamic Programming Backtracking Sorting Combinatorics

50.9% acceptance

Feb 25, 2026

1301

177

You are given an array nums of positive integers and a positive integer k. A subset of nums is beautiful if it does not contain two integers with an absolute difference equal to k. Return the number of non-empty beautiful subsets of the array nums. A subset of nums is an array that can be obtained by deleting some (possibly none) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn beautiful_subsets(mut nums: Vec<i32>, k: i32) -> i32 {
    // Backtracking: for each element, include it if nums[i]-k is not already in the subset.
    // Count all non-empty subsets.
    use std::collections::HashMap;
    nums.sort_unstable();
    let mut freq: HashMap<i32, i32> = HashMap::new();
    let mut count = 0i32;

    fn backtrack(idx: usize, nums: &[i32], k: i32, freq: &mut HashMap<i32, i32>, count: &mut i32) {
      for i in idx..nums.len() {
        let x = nums[i];
        if *freq.get(&(x - k)).unwrap_or(&0) == 0 {
          *freq.entry(x).or_insert(0) += 1;
          *count += 1;
          backtrack(i + 1, nums, k, freq, count);
          *freq.entry(x).or_insert(0) -= 1;
        }
      }
    }

    backtrack(0, &nums, k, &mut freq, &mut count);
    count
  }
}