LC-2597 Medium LeetCode

2597. The Number of Beautiful Subsets

Array Hash Table Math Dynamic Programming Backtracking Sorting Combinatorics

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 51% Topics: Array, Hash Table, Math, Dynamic Programming, Backtracking, Sorting, Combinatorics

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

import collections
import operator


# combinatorics, dp
class Solution(object):
    def beautifulSubsets(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def count(x):
            y = x
            while y-k in cnt:
                y -= k
            dp = [1, 0]  # dp[0]: count without i, dp[1]: count with i
            for i in xrange(y, x+1, k):
                dp = [dp[0]+dp[1], dp[0]*((1<<cnt[i])-1)]
            return sum(dp)

        cnt = collections.Counter(nums)
        return reduce(operator.mul, (count(i) for i in cnt.iterkeys() if i+k not in cnt))-1

Solution from kamyu104/LeetCode-Solutions · MIT