The Number of Beautiful Subsets

Medium
879.

The Number of Beautiful Subsets

The Number of Beautiful Subsets is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google and Intuit interviews.

A subset is beautiful when it contains no two elements whose absolute difference is exactly k.

Return the number of non-empty beautiful subsets of nums. Subsets are counted by the indices they use, so equal values at different positions give different subsets.

Example 1

Input
nums = [2,4,6], k = 2
Output
4
Explanation
The beautiful subsets are [2], [4], [6] and [2,6].

Example 2

Input
nums = [1], k = 1
Output
1

Example 3

Input
nums = [4,2,5,9,10,3], k = 1
Output
23

Constraints

  • 1 <= nums.length <= 20
  • 1 <= nums[i], k <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var beautifulSubsets = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

The Number of Beautiful Subsets — Problem & Solution

The Number of Beautiful Subsets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

The Number of Beautiful Subsets is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google and Intuit interviews.

Problem statement

A subset is beautiful when it contains no two elements whose absolute difference is exactly k.

Return the number of non-empty beautiful subsets of nums. Subsets are counted by the indices they use, so equal values at different positions give different subsets.

Example 1

Input: nums = [2,4,6], k = 2
Output: 4
Explanation: The beautiful subsets are [2], [4], [6] and [2,6].

Example 2

Input: nums = [1], k = 1
Output: 1

Example 3

Input: nums = [4,2,5,9,10,3], k = 1
Output: 23

Constraints

  • 1 <= nums.length <= 20
  • 1 <= nums[i], k <= 1000

Hints for The Number of Beautiful Subsets

  1. Hint 1

    Two values can conflict only if they are congruent modulo k, so the residue classes are independent.

  2. Hint 2

    Within a class, sort the distinct values; conflicts happen only between values exactly k apart — a chain.

  3. Hint 3

    Along a chain it is the House Robber recurrence, with each value contributing 2^count - 1 ways to pick at least one copy.

How to solve The Number of Beautiful Subsets

Split by residue modulo k. Different classes never conflict, so their counts multiply. Inside a class, sort the distinct values: the only forbidden pairs are consecutive values differing by exactly k, which is a path — the classic take-or-skip DP.

Approach

  1. Tally the multiplicity of each value and list the distinct values sorted.
  2. For each residue class, run a take/skip DP over its values: taking a value contributes 2^count - 1 (any non-empty choice of its copies) and, when the previous value is exactly k smaller, may only follow a skip.
  3. Multiply the per-class totals, then subtract 1 to drop the empty subset.

Why it works

|a - b| = k forces a ≡ b (mod k), so conflicts never cross residue classes and the classes are independent — hence the product. Within a class the sorted values form a path where each node conflicts only with its neighbours at distance k, and the take/skip recurrence counts independent sets on a path exactly. The 2^count - 1 factor accounts for equal values being distinguishable by index.

Complexity

  • Time — O(V²) over the distinct values
  • Space — O(V)

Pitfalls

  • Values equal to each other never conflict (their difference is 0, not k), so all their copies may be taken together.
  • Two values in the same class that are 2k apart do not conflict — only consecutive chain links do.
  • The empty subset must be subtracted at the end, once, not per class.

Reference solution

Python

from typing import List

def beautifulSubsets(nums: List[int], k: int) -> int:
    cnt = {}
    for x in nums:
        cnt[x] = cnt.get(x, 0) + 1
    vals = sorted(cnt)
    done = set()
    total = 1
    for v in vals:
        r = v % k
        if r in done:
            continue
        done.add(r)
        prev_skip, prev_take, prev_val, started = 1, 0, -1, False
        for u in vals:
            if u % k != r:
                continue
            ways = (1 << cnt[u]) - 1
            take = prev_skip * ways if (started and u - prev_val == k) else (prev_skip + prev_take) * ways
            skip = prev_skip + prev_take
            prev_skip, prev_take, prev_val, started = skip, take, u, True
        total *= prev_skip + prev_take
    return total - 1

Java

public static int beautifulSubsets(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : nums) cnt.merge(x, 1, Integer::sum);
    List<Integer> vals = new ArrayList<>(cnt.keySet());
    Collections.sort(vals);
    Set<Integer> done = new HashSet<>();
    long total = 1;
    for (int v : vals) {
        int r = v % k;
        if (!done.add(r)) continue;
        long prevSkip = 1, prevTake = 0;
        int prevVal = -1;
        boolean started = false;
        for (int u : vals) {
            if (u % k != r) continue;
            long ways = (1L << cnt.get(u)) - 1;
            long take = (started && u - prevVal == k) ? prevSkip * ways : (prevSkip + prevTake) * ways;
            long skip = prevSkip + prevTake;
            prevSkip = skip;
            prevTake = take;
            prevVal = u;
            started = true;
        }
        total *= prevSkip + prevTake;
    }
    return (int) (total - 1);
}

C++

int beautifulSubsets(vector<int>& nums, int k) {
    map<int, int> cnt;
    for (int x : nums) cnt[x]++;
    vector<int> vals;
    for (auto& p : cnt) vals.push_back(p.first);
    set<int> done;
    long long total = 1;
    for (int v : vals) {
        int r = v % k;
        if (done.count(r)) continue;
        done.insert(r);
        long long prevSkip = 1, prevTake = 0;
        int prevVal = -1;
        bool started = false;
        for (int u : vals) {
            if (u % k != r) continue;
            long long ways = (1LL << cnt[u]) - 1;
            long long take = (started && u - prevVal == k) ? prevSkip * ways : (prevSkip + prevTake) * ways;
            long long skip = prevSkip + prevTake;
            prevSkip = skip;
            prevTake = take;
            prevVal = u;
            started = true;
        }
        total *= prevSkip + prevTake;
    }
    return (int) (total - 1);
}

JavaScript

var beautifulSubsets = function(nums, k) {
    var cnt = {}, i;
    for (i = 0; i < nums.length; i++) cnt[nums[i]] = (cnt[nums[i]] || 0) + 1;
    var vals = Object.keys(cnt).map(Number).sort(function(a, b) { return a - b; });
    var done = {};
    var total = 1;
    for (var a = 0; a < vals.length; a++) {
        var r = vals[a] % k;
        if (done[r]) continue;
        done[r] = true;
        var prevSkip = 1, prevTake = 0, prevVal = -1, started = false;
        for (var b = 0; b < vals.length; b++) {
            var u = vals[b];
            if (u % k !== r) continue;
            var ways = (1 << cnt[u]) - 1;
            var take = (started && u - prevVal === k) ? prevSkip * ways : (prevSkip + prevTake) * ways;
            var skip = prevSkip + prevTake;
            prevSkip = skip;
            prevTake = take;
            prevVal = u;
            started = true;
        }
        total *= prevSkip + prevTake;
    }
    return total - 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets