Python | Simple Recursion + Memoization | Subset Sum with Length Count
Intuition\nThis problem is clearly a variant of the Subset Sum Problem. The difference is that instead of checking if there is a subset of nums that sums to k w
# Intuition\nThis problem is clearly a variant of the [Subset Sum Problem](https://en.wikipedia.org/wiki/Subset_sum_problem). The difference is that instead of checking if there is a subset of `nums` that sums to `k` we want the number of subsequences that contain subsets that sum to `k`.\n\nConsider a subset `L` of `nums` that sums to `k`, in how many subsequences is it contained? Clearly, in all subsequences that contain it. More precisely, if `L` has length $t$, there are $n-t$ elements in `K = nums \\ L` (that is, in `nums` with `L` removed). For each subset of `K` (from the empty list to `K` itself) we get one subsequence containing `L`. Thus, `L` contributes $2^{n-t}$ subsequences to the total result.\n\nTo solve the problem we simply compute all subsets `L` that sum to `k` along with their respective size.\n\n# Approach\nGiven `nums` and `k`, we are basically presented with two choices:\n- Take `nums[0]` into our subset, in which case we recursively solve the problem for `nums[1:]` and `k-nums[0]` (and remember to increase our subset size by $1$).\n- Not take `nums[0]` into our subset, in which case we recursively solve the problem for `nums[1:]` and `k`.\n\nAs for edge cases:\n- If `k = 0` then we are done and we return $2^{n-t}$ where $t$ is our subset size.\n- If `k < 0` there are no solutions as all numbers in `nums` are positive and we return `0`.\n- If `nums = []` (and `k != 0`) there are also clearly no solutions and we return `0`.\n\nWe remark that to speed up the implementation we can use an index `i` to denote the starting index of `nums` instead of performing expansive slices on the list:\n\n# Code\n```\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        M = 10**9+7\n        def rec(nums, i, k, cnt, d):\n            n = len(nums)\n            key = i, k, cnt\n            if key in d: return d[key]\n            # If we reach the target, add number of subsequences\n            # containing the cnt items \n            if k == 0:\n                d[key] = (2**(n-cnt)) % M\n                return d[key]\n            # If list is empty or target is negative\n            # we can\'t reach the target\n            if i == n or k < 0: return 0\n            \n            res = 0\n            # Don\'t take current item\n            res += rec(nums, i+1, k, cnt, d)\n            # Take current item\n            res += rec(nums, i+1, k-nums[i], cnt+1, d)\n\n            d[key] = res % M\n            return d[key]\n            \n        return rec(nums, 0, k, 0, dict())\n```\n\n# Complexity\n- Time complexity: The runtime of the `rec` is $O(1)$ (not accounting for the runtime of recursive calls). The input is specified by `i, k, cnt`, as all three variables are bounded by $n$, the total runtime is $O(n^3)$.\n\n- Space complexity: The recursive stack has depth $O(n)$ with $O(1)$ space required for each call, thus the total space required is $O(n)$.\n
['Recursion', 'Memoization', 'Combinatorics', 'Python3']