🐱‍💻Simple DP || Short Concise Code || Well Explained
Intuition\n- The basic approach is that the power of a subsequence is the number of times that subsequence occurs as a subsequence in all the possible susequenc
# Intuition\n- The basic approach is that the power of a subsequence is the number of times that subsequence occurs as a subsequence in all the possible susequences of the given array;\n- On some observation, you can see that a subsequence with target sum of length "len" will occur a total of 2^(n-len) times as a subsequence of all possible subsequences.\n- It might sound to be a little confusing at first, but thats why the problem is marked to be hard..\n- Give the statement another read you\'ll get it what im trying to say.\n\n# Approach\n- Simply use recursion for finding the subsequences, then memoize.. Just keep in mind the situations where the overflow can happen (while calculating pow(2,x) and while adding up;\n- a -> taking the current element nums[ind]\n- b -> not taking the current element nums[ind]\n- Used a custom poww fn to avoid overflows\n- A subsequence with target sum of length "len" will occur a total of 2^(n-len) times as a subsequence of all possible subsequences.\n\n# Complexity\n- Time complexity:\nO(n^3)\n\n- Space complexity:\nO(n^3)\n\n# Code\n```\n#define ll long long\nll mod=1e9+7;\n\nclass Solution {\npublic:\n    map<ll,map<ll,map<ll,ll>>> dp;\n    \n    ll poww(ll a,ll b){\n        ll out=1;\n        while(b--){\n            out = ((out%mod) * (a%mod))%mod;\n        }\n        return out%mod;\n    }\n    \n    ll helper(vector<int> &nums,int n,int k,int ind,int len,int sum){\n        if(sum==k) return poww(2,n-len);\n        if(sum>k || ind==n) return 0;\n        if(dp.count(ind) && dp[ind].count(len) && dp[ind][len].count(sum)) return dp[ind][len][sum];\n        \n        ll a = helper(nums,n,k,ind+1,len+1,sum+nums[ind]);\n        ll b = helper(nums,n,k,ind+1,len,sum);\n        \n        return dp[ind][len][sum] = (a%mod + b%mod)%mod;\n    }\n    \n    int sumOfPower(vector<int>& nums, int k) {\n        int n=nums.size();\n        return helper(nums,n,k,0,0,0);\n    }\n};\n```\n![upvote xd.jpeg](https://assets.leetcode.com/users/images/4c93a3b8-0775-4005-b37d-d9d892cfcbe6_1710605331.7995887.jpeg)\n
['Math', 'Dynamic Programming', 'Memoization', 'C++']