Kotlin - Bottom Up DP Solution (Beats 100%) (Intuitive Explanation)
Intuition: \nIf we\'re able to find a combination (of size "cnt") that sums up to "k" then, we can easily find its contribution in the final answer (i.e. total 
**Intuition:** \nIf we\'re able to find a combination (of size "cnt") that sums up to "k" then, we can easily find its contribution in the final answer (i.e. total original subsequences where this combination is present).\nThis way, our problem can be reduced to **finding the number of combinations that sum up to the value "k"**.\n        \nFor e.g. For the array [1,2,3] and k = 3\nWe\'ve two combinations which sum up to k=3\na.) [1,2] and\nb.) [3]\n\nNow, we can say that combination [1,2] will occur in 2^(n-cnt) subsequences (i.e. 2^(3-2) = 2) subsequences of array [1,2,3].\nWhy? Because remember how we calculate the count of possible subsequences of an array.\n=> By multiplying with 2 at every position (as we have 2 options i.e. take/skip at every position)\n\nNow, for our combination we know that "cnt" elements have to occur in the subsequence.\nSo, we can only have 2 options for remaining elements (i.e. n - cnt) elements\nTherefore, **contribution (by combination of size "cnt") = 2^(n-cnt)**\n        \nPossible subsequences for [1,2] = 2^(3-2) = 2\na.) [1,2]\nb.) [1,2,3]\n\nPossible subsequences for [3] = 2^(3-1) = 4\na.) [3]\nb.) [1,3]\nc.) [2,3]\nd.) [1,2,3]\n\n\n**DP Approach:**\nLet dp[i][sum][count] = number of unique combinations from (1,i) position with sum equal to "sum" and number of elements equal to "count" then,\n\ndp[i][sum][count] = \n1. dp[i-1][sum][count] => skip the "ith" element\n2. dp[i-1][sum-nums[i]][count-1] => take the "ith" element\n\nbase case: dp[i][0][0] = 1\n(When sum=0 and count=0 that means we\'ve found a valid combination)\n\nFinally ans = summation of below values:\na). 2^(n-1) * dp[n][k][1] + \nb). 2^(n-2) * dp[n][k][2] + \nc). ... + \nn). 2^(n-n) * dp[n][k][n] \n\n**Time Complexity:**\nO(n * n * k)\n\n**Space Complexity:**\nO(n * n * k)\n\n**Code:**\n```kotlin\nclass Solution {\n    val MOD = 1000000007\n    val dp = Array(101) { Array(101) { LongArray(101) { 0L } } }\n    \n    fun sumOfPower(nums: IntArray, k: Int): Int {\n        val n = nums.size\n        dp[0][0][0] = 1\n        \n        for (i in 1..n) {\n            //dp[i][0][0] = 1\n            for (sum in 0..k) {\n                for (count in 0..n) {\n                    // skip\n                    dp[i][sum][count] += dp[i-1][sum][count] % MOD\n                    \n                    // take\n                    val num = nums[i-1]\n                    if (sum >= num && count >= 1) {\n                        dp[i][sum][count] += dp[i-1][sum-num][count-1] % MOD\n                    }\n                    dp[i][sum][count] = dp[i][sum][count] % MOD\n                }\n            }\n        }\n        \n        var ans: Long = 0L\n        var pow2: Long = 1L\n        for (len in n downTo 1) {\n            ans += (pow2 * 1L * dp[n][k][len]) % MOD\n            ans %= MOD\n            //println("dp[$n][$k][$len]: ${dp[n][k][len]}")\n            pow2 = (2*pow2) % MOD\n        }\n        return ans.toInt()\n    }\n}\n```
['Dynamic Programming', 'Kotlin']