2597. The Number of Beautiful Subsets - Explanation

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        def helper(i, count):
            if i == len(nums):
                return 1

            res = helper(i + 1, count)  # Skip nums[i]
            if not count[nums[i] + k] and not count[nums[i] - k]:
                count[nums[i]] += 1
                res += helper(i + 1, count)
                count[nums[i]] -= 1

            return res

        return helper(0, defaultdict(int)) - 1

class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        cnt = Counter(nums)
        groups = []  # List of dicts
        cache = {}

        def helper(n, g):
            if n not in g:
                return 1
            if n in cache:
                return cache[n]

            skip = helper(n + k, g)
            include = (2**g[n] - 1) * helper(n + 2 * k, g)
            cache[n] = skip + include
            return skip + include

        visit = set()
        for n in cnt.keys():
            if n in visit:
                continue
            g = {}
            while n - k in cnt:
                n -= k
            while n in cnt:
                g[n] = cnt[n]
                visit.add(n)
                n += k
            groups.append(g)

        res = 1
        for g in groups:
            n = min(g.keys())
            res *= helper(n, g)

        return res - 1

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

        visit = set()
        for n in cnt.keys():
            if n in visit:
                continue
            g = {}
            while n - k in cnt:
                n -= k
            while n in cnt:
                g[n] = cnt[n]
                visit.add(n)
                n += k
            groups.append(g)

        res = 1
        for g in groups:
            dp = {}
            prev = None

            for num in sorted(g):
                count = g[num]
                if prev is None or prev + k != num:
                    dp[num] = (dp.get(prev, 1) * (1 + (2 ** count - 1)))
                else:
                    dp[num] = dp[prev] + (2 ** count - 1) * dp.get(prev - k, 1)
                prev = num

            res *= dp[prev]

        return res - 1

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