The Number of Beautiful Subsets

Medium · Backtracking · Explanation and code example

Dynamic Programming (Space Optimized)

How it works

We can optimize space by observing that we only need information from the previous two positions in each chain. Instead of storing results for all numbers in a DP map, we use two variables: one for subsets that include the previous number (dp) and one for subsets that do not include it (ndp).

By grouping numbers based on their remainder when divided by k, we naturally partition them into non-interacting groups. Numbers with different remainders can never conflict since their difference cannot be exactly k.

Steps

  1. Group numbers by num % k to identify independent chains.
  2. For each group, sort numbers and process them with two state variables: dp (subsets including some copies of the previous number) and ndp (subsets not including the previous number).
  3. For each number with count c, compute have = 2^c - 1 (ways to include at least one copy).
  4. If the current number is not adjacent to the previous in the chain, we can combine have with both dp and ndp.
  5. If adjacent, we can only combine have with ndp.
  6. Update ndp to include the old dp (representing subsets that skip the current number).
  7. Multiply (dp + ndp) across all groups and subtract 1.

Complexity

  • Time complexity: O(n log n)
  • Space complexity: O(n)

Python code example

from typing import List
from collections import Counter, defaultdict

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        cnt = Counter(nums)
        groups = defaultdict(dict)

        # Group numbers based on their remainder with k
        for num in nums:
            groups[num % k][num] = cnt[num]

        res = 1
        for g in groups.values():
            prev = 0
            dp, ndp = 0, 1

            for num in sorted(g.keys()):
                count = g[num]
                have = (1 << count) - 1
                tmp = ndp
                ndp += dp

                if prev == 0 or prev + k != num:
                    dp = have * (tmp + dp)
                else:
                    dp = tmp * have

                prev = num

            res *= (dp + ndp)

        return res - 1

C++ code example

class Solution {
public:
    int beautifulSubsets(vector<int>& nums, int k) {
        unordered_map<int, map<int, int>> groups;
        unordered_map<int, int> cnt;
        for (int& num : nums) {
            cnt[num]++;
        }

        // Group numbers based on remainder with k
        for (int num : nums) {
            groups[num % k][num] = cnt[num];
        }

        int res = 1;
        for (auto& [rem, g] : groups) {
            int prev = 0, dp = 0, ndp = 1;

            for (auto& [num, count] : g) {
                int have = (1 << count) - 1;
                int tmp = ndp;
                ndp += dp;

                if (prev == 0 || prev + k != num) {
                    dp = have * (tmp + dp);
                } else {
                    dp = tmp * have;
                }

                prev = num;
            }

            res *= (dp + ndp);
        }

        return res - 1;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations