Java dfs(r) - dfs(l-1) = ans
Intuition\n1. reorder the nums into: uniqueNums and cnt, resolv the multi-set problem\n2. make dfs(at, target) means index at i, remain sum = target, return how
# Intuition\n1. reorder the nums into: uniqueNums and cnt, resolv the multi-set problem\n2. make dfs(at, target) means index at i, remain sum = target, return how many ans in it\n3. return dfs(r) - dfs(l-1) = ans\n\n# Approach\ntwo key point in dfs:\n\n    def dfs(at, target)\n        # 1. do not select nums[at]\n        total += dfs(at+1, target)\n\n        # 2. how many count nums[at], use it in 1 ~ count times\n        # for example, [1,2,2,3] there are 2 and count of 2\n        total += dfs(at+1, target - (2*1)) # use 1 of nums[at]\n        total += dfs(at+1, target - (2*2)) # use 2 of nums[at]\n        ... for ...\n\n        return total\n\n\n# Complexity\n- Time complexity:\nn = len(nums)\nm = max(l, r, sum(nums))\nO(n*m)\n\nthere a super ticky input that is r > sum(nums)\nmake array of 20001 x 20001 will OOM\n\n- Space complexity:\nO(n*m)\n\n# Code\n```\nclass Solution {\n    long MOD00 = 100000000700L;\n    long dp[][] = null ;\n    \n    public int countSubMultisets(List<Integer> nums, int l, int r) {\n        long MOD = 1000000007;\n        \n        int sum = 0;\n        Map<Integer, Integer> cnt = new HashMap<>();\n        for (int num : nums) {\n            cnt.put(num, cnt.getOrDefault(num, 0) + 1);\n            sum += num;\n        }\n        \n        int[] uniqueNums = new int[cnt.size()];\n        int index = 0;\n        for (int key : cnt.keySet()) {\n            uniqueNums[index] = key;\n            index++;\n        }\n        \n        Arrays.sort(uniqueNums);\n        int n = uniqueNums.length;\n\n        sum = Math.max(sum, r);\n        dp = new long[uniqueNums.length][sum+1] ;\n        \n        long rr = dfs(0, r, uniqueNums, cnt, n);\n        long ll = dfs(0, l - 1, uniqueNums, cnt, n);\n        System.out.println("lr = " + rr + " " + ll);\n        return (int) ((MOD00 + rr - ll) % MOD);\n    }\n\n    private long dfs(int at, int target, int[] uniqueNums, Map<Integer, Integer> cnt, int n) {\n        if (target < 0) {\n            return 0;\n        }\n\n        if (at >= n) {\n            return 1;\n        }\n        \n        if (dp[at][target] != 0) {\n            return dp[at][target] ;\n        }\n\n        long total = 0;\n        // not choose at\n        total += dfs(at + 1, target, uniqueNums, cnt, n);\n        // choose at\n        int count = cnt.get(uniqueNums[at]);\n        for (int i = 1; i <= count; i++) {\n            total += dfs(at + 1, target - uniqueNums[at] * i, uniqueNums, cnt, n);\n        }\n\n        dp[at][target] = total % MOD00 ;\n        return dp[at][target] ;\n    }\n    \n}\n```
['Memoization', 'Java']