Video Solution | Python3 Easy 3D DP | 01 Knapsack Problem
https://www.youtube.com/watch?v=K8us3YZSVkc\n\n# Intuition\nThe problem description makes it seem like we need to generate all subsequences of the Array, and th
https://www.youtube.com/watch?v=K8us3YZSVkc\n\n# Intuition\nThe problem description makes it seem like we need to generate **all** subsequences of the Array, and then for all of those generate subsequences find **their** subsequences that equal K.\n\nThis is overly complicated and confusing so it helps to reframe how we are thinking about the problem. Instead we can think, if we see a subsequence that has a sum equal to 3, **how many other subsequences can this subsequence be a part of.**\n\nTo get this value, we can use the formula 2**(len(nums) - len(subsequence)).\n\n# Approach\n- Generate all subsequences of the array using an 01 Knapsack style recursive function\n- When our index reaches the end of the array\n  - if the current subsequence has a sum == k, we add 2**(len(nums) - len(subsequence)) to our answer\n  - otherwise return 0\n\n# Complexity\n- Time complexity: O(n^2 * k)\n\n\n- Space complexity: O(n^2 * k)\n\n# Code\n```\nfrom functools import cache\n\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        \n        @cache\n        def find_sum(index, current_sum, current_length):\n            if index >= len(nums):\n                if current_sum == k:\n                    return 2**(len(nums) - current_length)\n                return 0\n\n            if current_sum > k:\n                return 0\n            \n            take = find_sum(index + 1, current_sum + nums[index], current_length + 1)\n            not_take = find_sum(index + 1, current_sum, current_length)\n\n            return take + not_take\n\n        return find_sum(0, 0, 0) % 1000000007\n```
['Python3']