Clean DP Tabulation + Combinatorics | Explained | C++
- Intuition :\n\n - For Every length = [1 , N] , find number of subsequences with Sum = K ( Compute Using Dynamic Programming)\n- Now its a Simple Combinatorics
### ***- Intuition :***\n\n - For Every length = [1 , N] , find number of subsequences with Sum = K ( Compute Using Dynamic Programming)\n- Now its a Simple Combinatorics Problem \n- Say Length = L then dp[L][K] stores number of subsequences with length = L and Sum = K\n- Now this \'L\' Length Subsequence can be Combined with (N-L) elements in 2^(N-L) ways each generating a new subsequence\n\n\n\n### ***- Time complexity : O(N * N * K)***\n### ***- Space complexity : O(N * K)***\n\n# Code\n```\nclass Solution {\nprivate:\n    const int mod = 1e9 + 7;\n\n    long long power(long long a,long long b){\n        long long res = 1;\n        while(b){\n            if(b&1) res = (res * a) % mod;\n            a = (a * a) % mod;\n            b >>= 1;\n        }\n        return res;\n    }\n\npublic:\n    int sumOfPower(vector<int>& nums, int k){\n        int n = nums.size();\n        vector<vector<long long>> dp(n+1,vector<long long>(k+1,0));\n        dp[0][0] = 1;\n        for(int pos = 1 ; pos <= n ; pos++){\n            for(int len = pos ; len >= 1 ; len--){\n                for(int sum = nums[pos-1] ; sum <= k ; sum++){\n                    dp[len][sum] = (dp[len][sum] + dp[len-1][sum-nums[pos-1]] ) % mod;\n                }\n            }\n        }\n        long long ans = 0;\n        for(int len = 1 ; len <= n ; len++) ans = (ans + dp[len][k] * power(2,n-len)) % mod;\n        return ans;\n    }\n};\n\n```
['C++']