Rust/C++ DP with Optimized Double Loop
Intuition\n Describe your first thoughts on how to solve this problem. \nNoticed that the sum of all numbers is no more 20000. When we add the numbers in sunseq
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nNoticed that the sum of all numbers is no more 20000. When we add the numbers in sunsequences, their sums are slowly growing to the up bound, which is no more than 20000.\nWe will use an array int dp[20001] to track the frequencies of the sums. We set dp[0] = 1 (empty sub-sequence) and everything else to 0 initially.\nWe then different count, uo to its frequency, of the same number for making different subsequences. Instead of tracking the nubers of different sequences, we track the frequences of their sums.\nIf upBound is the total sum of the numbers processed so far, then dp[k] == 0 for k > upBound. Therefore, we only need to loop to upBound.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n//Rust\nuse std::collections::BTreeMap;\nimpl Solution {\n    pub fn count_sub_multisets(nums: Vec<i32>, l: i32, r: i32) -> i32 {\n        let mut mp = BTreeMap::<i32, i32>::new();\n        let mut count0 = 0i64;\n        for a in nums { \n            if a == 0 { count0 += 1; }\n            else { *mp.entry(a).or_insert(0) += 1; }\n        }\n        \n        let mut dp = vec![0; 20001];\n        let mut sum = 0;\n        let MOD = 1_000_000_007;\n\n        dp[0] = 1;\n        for (val, cnt) in &mp {\n            for j in (0..= sum).rev() {\n                for k in 1 ..= (*cnt) as usize {\n                    let it = j + k * (*val) as usize;\n                    dp[it] = (dp[it] + dp[j]) % MOD;\n                }\n            }\n            sum += (*val) as usize * (*cnt) as usize;\n        }\n\n        let mut ret = 0;\n        for i in l as usize ..= r as usize {\n            ret = (ret + dp[i]) % MOD;\n        }\n\n        (ret as i64 * (count0 + 1) % MOD as i64) as _ \n    }\n}\n```\n~~~\n//C++\nlong long dp[20001];\nclass Solution {\npublic:\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n        map<int, int> mp;\n        \n        for (auto &a: nums) ++mp[a];\n        memset(dp, 0, sizeof(dp));\n        dp[0] = 1;\n        \n        int sum = 0, mod = 1000000007;\n        for (auto &it: mp) {\n            if (it.first == 0) continue;\n            \n            for (int j = sum; j >= 0; --j) {\n                for (int k = 1; k <= it.second; ++k) {\n                    dp[j + k * it.first] = (dp[j + k * it.first] + dp[j]) % mod;\n                }\n            }\n            sum += it.second * it.first;\n        }\n        \n        int ret = 0;\n        for (int i = l; i <= r; ++i) {\n            ret = (ret + dp[i]) % mod; \n        }\n        \n        return 1LL * ret * (mp[0] + 1) % mod;\n    }\n};\n~~~
['Rust']