The Number of Beautiful Subsets — Medium Problem & Solution

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.

Difficulty: Medium
Topics: Arrays, Hash Table, Dynamic Programming, Backtracking
Asked at: Amazon, Google, Intuit
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

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

Tally the multiplicity of each value and list the distinct values sorted.
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.
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue