💥💥 Beats 100% on runtime and memory [EXPLAINED]
IntuitionFind the number of subsequences in an array whose sum is equal to a given value k. I need to count the subsequences that can be formed by either includ
# Intuition
Find the number of subsequences in an array whose sum is equal to a given value k. I need to count the subsequences that can be formed by either including or excluding each element of the array. This can be broken down into a dynamic programming problem where I compute the number of ways to achieve a specific sum from the current element to the end of the array.

# Approach
I use a recursive function with memoization (dynamic programming) to calculate the number of subsequences that add up to k. For each element in the array, I have two choices: either I include the element in the subsequence or I exclude it. I keep track of the number of subsequences for each combination of index i and sum k in a 2D array dp where dp[i][k] stores the result. If I’ve already computed a value for a particular combination, I return the precomputed value.

# Complexity
- Time complexity:
O(n * k) because I’m calculating the result for every combination of index i and sum k. Each function call only explores two choices (include or exclude the current element), leading to a linear pass through the array and sums up to k.

- Space complexity:
O(n * k) because of the memoization table dp that stores results for each index and sum combination. This table grows with the number of elements in the array (n) and the target sum (k).

# Code
```kotlin []
class Solution {
    val mod = 1e9.toLong() + 7
    var n = 0
    var k = 0
    val dp = Array(101) { IntArray(101) { -1 } }

    // Function to compute the number of subsequences for a given index and sum
    fun f(i: Int, k: Int, nums: IntArray): Int {
        if (k == 0) return pow2(n - i) // Base case: if sum is 0, return 2^(n-i)
        if (i >= n || k < 0) return 0 // Base case: out of bounds or negative sum
        if (dp[i][k] != -1) return dp[i][k] // Return precomputed result if exists

        var ans = 2L * f(i + 1, k, nums) % mod // Count subsequences without including nums[i]
        if (k >= nums[i]) // If the current element can be part of the subsequence
            ans = (ans + f(i + 1, k - nums[i], nums)) % mod // Count subsequences including nums[i]
        
        dp[i][k] = ans.toInt() // Save the result for future reference
        return dp[i][k] // Return the calculated value
    }

    // Function to calculate the modular exponentiation
    fun powMod(B: Long, exp: Int): Int {
        if (exp == 0) return 1 // Base case: anything raised to 0 is 1
        var y = if (exp and 1 == 1) B else 1L // If exponent is odd, multiply by base
        return (powMod(B * B % mod, exp / 2) * y % mod).toInt() // Recursively compute power
    }

    // Function to calculate 2^exp % mod efficiently
    fun pow2(exp: Int): Int {
        if (exp < 30) return (1 shl exp) // Direct computation for small exponents
        val (q, r) = div(exp, 30) // Split exponent into quotient and remainder
        val B = (1 shl 30) - mod // Calculate base value for large exponents
        return (powMod(B, q) * (1L shl r) % mod).toInt() // Combine the results
    }

    // Main function to compute the sum of powers for given nums array and k
    fun sumOfPower(nums: IntArray, k: Int): Int {
        n = nums.size
        this.k = k
        return f(0, k, nums) // Start the computation from the first index
    }
    
    // Helper function to divide two integers and return quotient and remainder
    fun div(a: Int, b: Int): Pair<Int, Int> {
        val q = a / b
        val r = a % b
        return Pair(q, r) // Return quotient and remainder
    }
}

```
['Array', 'Math', 'Dynamic Programming', 'Depth-First Search', 'Memoization', 'Combinatorics', 'Kotlin']