2D DP accepted solution Java
\n# Code\n\nclass Solution {\n\n    int MOD = (int) 1e9 + 7;\n\n    HashMap<Integer, Integer> map;\n\n    int dp[][];\n\n    int solve(ArrayList<Integer> al, in
\n# Code\n```\nclass Solution {\n\n    int MOD = (int) 1e9 + 7;\n\n    HashMap<Integer, Integer> map;\n\n    int dp[][];\n\n    int solve(ArrayList<Integer> al, int l, int r, int index, int sum) {\n        if (sum > r) {\n            return 0;\n        }\n\n        long ans = 0;\n\n        // if (sum >= l && sum <= r) {\n        // ans = ans + 1;\n        // }\n\n        if (index >= al.size()) {\n            return (int) ans;\n        }\n\n        if (dp[index][sum] != -1) {\n            return dp[index][sum];\n        }\n\n        int cur = al.get(index);\n        int count = map.get(cur);\n\n        for (int i = 0; i <= count; i++) {\n            int curSum = sum + cur * i;\n\n            if (curSum > r) {\n                break;\n            }\n\n            ans = ans + solve(al, l, r, index + 1, curSum);\n\n            if (i != 0 && curSum >= l && curSum <= r) {\n                ans = ans + 1;\n            }\n\n            ans = ans % MOD;\n        }\n\n        dp[index][sum] = (int) ans;\n\n        return (int) ans;\n    }\n\n    public int countSubMultisets(List<Integer> nums, int l, int r) {\n        map = new HashMap<>();\n\n        ArrayList<Integer> al = new ArrayList<>();\n\n        for (int i = 0; i < nums.size(); i++) {\n            int cur = nums.get(i);\n\n            int count = map.getOrDefault(cur, 0) + 1;\n            map.put(cur, count);\n\n            if (count == 1) {\n                al.add(cur);\n            }\n        }\n\n        int n = al.size();\n\n        dp = new int[n][r + 1];\n\n        for (int i = 0; i < dp.length; i++) {\n            for (int j = 0; j < dp[0].length; j++) {\n                dp[i][j] = -1;\n            }\n        }\n\n        Collections.sort(al);\n\n        int ans = solve(al, l, r, 0, 0);\n\n        if (l == 0) {\n            ans = ans + 1;\n        }\n\n        ans = ans % MOD;\n\n        return ans;\n    }\n}\n```
['Dynamic Programming', 'Java']