[Python] House Robber, O(n)
Explanation\nSplit A[i] into different group by the value of A[i] % k.\nCount the frequency of A[i].\nSort A[i] and then do 198. House Robber.\n\ndp0 is the way
# **Explanation**\nSplit `A[i]` into different group by the value of `A[i] % k`.\nCount the frequency of `A[i]`.\nSort `A[i]` and then do [198. House Robber](https://leetcode.com/problems/house-robber/).\n\n`dp0` is the ways that without `A[i]`\n`dp1` is the ways that with `A[i]`\n<br>\n\n# **Complexity**\nTime `O(nlogn + k)`\nSpace `O(n + k)`\n<br>\n\n**Python**\n```py\n    def beautifulSubsets(self, A: List[int], k: int) -> int:\n        count = [Counter() for i in range(k)]\n        for a in A:\n            count[a % k][a] += 1\n        res = 1\n        for i in range(k):\n            prev, dp0, dp1 = 0, 1, 0\n            for a in sorted(count[i]):\n                v = pow(2, count[i][a])\n                if prev + k == a:\n                    dp0, dp1 = dp0 + dp1, dp0 * (v - 1)\n                else:\n                    dp0, dp1 = dp0 + dp1, (dp0 + dp1) * (v - 1)\n                prev = a\n            res *= dp0 + dp1\n        return res - 1\n```\n<br>\n\n# Solution 2\nInspired by @yawn_sean,\nContinue to optimize the solution 1.\nIn solution 1, we sort elements by remainder,\nto get the house robber input array.\nActually we can check if `count[a + k] > 0`,\nand find out the last element for arithmetic sequence.\n\nCount the frequency of `A`,\nand then consider all the arithmetic sequence with difference `k`.\n\nEach arithmetic sequence can be solve as a hourse robber problem.\nWe solve the hourse robber by `dp`.\n`dp(a)` return the result for sequence no bigger than `a`.\n\n`dp(a)[0]` is the ways that without `a`\n`dp(a)[1]` is the ways that with `a`\n\n`dp(a)[0] = dp(a - k)[0] + dp(a - k)[1]`\n`dp(a)[1] = dp(a - k)[0] * (2 ^ count(a) - 1`\n\n\n**Python**\n```py\n    def beautifulSubsets(self, A: List[int], k: int) -> int:\n        count = Counter(A)\n\n        def dp(a):\n            dp0, dp1 = dp(a - k) if a - k in count else (1, 0)\n            return dp0 + dp1, dp0 * (pow(2, count[a]) - 1)\n\n        return reduce(mul, (sum(dp(a)) for a in count if not count[a + k])) - 1\n```\n
[]