[python] O(n)
Intuition\nwe have to notice that the only elements that affect one another are those that exist in a streak of numbers that differ by k.\n\n# Approach\ni group
# Intuition\nwe have to notice that the only elements that affect one another are those that exist in a streak of numbers that differ by k.\n\n# Approach\ni group these numbers together into these streaks, and find the number of subsets of each streak separately. we can then multiply the answers together, since all streak subsets are compatible with one another.\n\n# Code\n```\nclass Solution:\n    def beautifulSubsets(self, nums: List[int], k: int) -> int:    \n        @cache\n        # ways of choosing from streaks[si][i:]\n        def ways(i, si):\n            if i >= len(streaks[si]):\n                return 1\n            # there are 2**rep-1 ways of choosing at least \n            # one of streak[i].\n            return ways(i+1, si) + (2**reps[streaks[si][i]]-1) * ways(i+2, si)\n        \n        reps = defaultdict(int)\n        mark = {} # -1 for start of streak, 1 otherwise\n\n        for num in nums:\n            mark[num] = -1\n\n        for num in nums:\n            if reps[num]:\n                reps[num] += 1\n            else:\n                if num - k in mark:\n                    mark[num] = 1\n                reps[num] = 1\n\n        streaks = []\n        for num in nums:\n            if num not in mark or mark[num] == 1:\n                continue\n            curr = num\n            streaks.append([])\n            while curr in mark:\n                streaks[-1].append(curr)\n                del mark[curr]\n                curr = curr + k\n        \n        prod = 1\n        for i in range(len(streaks)):\n            prod *= ways(0, i)\n        return prod - 1 # don\'t consider empty subset\n```
['Dynamic Programming', 'Python3']