[Python/Rust] Knapsack
What matters here are lengths L of subsequences that sum up to k. Once we obtain such a subsequence, the number of all subsequences that include that subsequenc
What matters here are lengths `L` of subsequences that sum up to `k`. Once we obtain such a subsequence, the number of all subsequences that include that subsequence is `2**(len(nums)-L)`, i.e., calculated by considering all possible cases for taking / not-taking each of remaining numbers.\n\nTo compute the above described sum, each number should be considered as either belonging to a k-summable subsequence or not. When bruteforcing all possible combinations using a classical knapsack-type DP, we will be hitting cases where `kk=0`, i.e., k-summable subsequences. For them, each summand would contribute a factor of `1`, and each non-summand would contribute a factor of `2`. The product of these factors would give the total number of subsequences that include the found k-summable subsequence.\n\n```python []\nclass Solution:\n    def sumOfPower(self, nums: List[int], k: int) -> int:\n        \n        @cache\n        def dfs(i, kk):\n            if kk == 0                  : return 2**(len(nums)-i)\n            if kk < 0 or i >= len(nums) : return 0\n            return 1 * dfs(i+1, kk-nums[i]) + 2 * dfs(i+1, kk)\n\n        return dfs(0,k) % (10**9 + 7)\n```\n```rust []\nuse std::collections::HashMap;\n\nimpl Solution\n{\n    pub fn sum_of_power(nums: Vec<i32>, k: i32) -> i32\n    {\n        const MOD : i32 = 1_000_000_007;\n\n        // fast exponentiation with modulus\n        fn mod_pow(base: i32, mut exp: i32, m: i32) -> i32\n        {\n            let mut result: i64 = 1;\n            let mut base: i64 = base as i64;\n            let m: i64 = m as i64;\n\n            base %= m;\n            while exp > 0\n            {\n                if exp % 2 == 1\n                {\n                    result = (result * base) % m;\n                }\n                base = (base * base) % m;\n                exp >>= 1;\n            }\n            result as i32\n        }\n\n        // knapsack DP\n        fn dfs(i: usize, kk: i32, nums: &Vec<i32>, cache: &mut HashMap<(usize,i32),i32>) -> i32\n        {\n            if let Some(&result) = cache.get(&(i, kk)) { return result; }\n\n            let result = \n                if      kk == 0 { mod_pow(2, (nums.len() - i) as i32, MOD) }\n                else if kk  < 0 || i >= nums.len() { 0 } \n                else \n                {\n                    (1 * dfs(i+1, kk-nums[i], nums, cache) % MOD +\n                    2 * dfs(i+1, kk, nums, cache) % MOD) % MOD\n                };\n            \n            cache.insert((i, kk), result);\n            result\n        }\n\n        dfs(0, k, &nums, &mut HashMap::new())\n    }\n}\n```\n
['Python3']