Recursion->Memo->DP, not best solution, no explanation.
Intuition\nIn order to understand DP better for DP newbie :)\n\n# Recursion (TLE)\n\nclass Solution {\n    int mod = 1_0000_0000_7;\n    public int countSubMult
# Intuition\nIn order to understand DP better for DP newbie :)\n\n# Recursion (TLE)\n```\nclass Solution {\n    int mod = 1_0000_0000_7;\n    public int countSubMultisets(List<Integer> nums, int l, int r) {\n        Map<Integer, Integer> map = new HashMap<>();\n        for (int num : nums) {\n            map.put(num, map.getOrDefault(num, 0) + 1);\n        }\n        List<Pair<Integer, Integer>> list = new ArrayList<>();\n        for (int key : map.keySet()) {\n            list.add(new Pair<>(key, map.get(key)));\n        }\n        \n        return helper(l, r, 0, list, 0);\n    }\n\n    int helper(int l, int r, int sum, List<Pair<Integer, Integer>> list, int index) {\n        if (index >= list.size()) return l <= sum && sum <= r ? 1 : 0;\n        Pair<Integer, Integer> pair = list.get(index);\n        int key = pair.getKey(), val = pair.getValue();\n        int res = 0;\n        for (int j = 0; j <= val; j++) {\n            res = (res + helper(l, r, sum + j*key, list, index+1)) % mod;\n        }\n        return res;\n    }\n}\n```\n\n# Memo (Pass)\n```\nclass Solution {\n    int mod = 1_0000_0000_7;\n    public int countSubMultisets(List<Integer> nums, int l, int r) {\n        Map<Integer, Integer> map = new HashMap<>();\n        int sum = 0;\n        for (int num : nums) {\n            map.put(num, map.getOrDefault(num, 0) + 1);\n            sum += num;\n        }\n        List<Pair<Integer, Integer>> list = new ArrayList<>();\n        for (int key : map.keySet()) {\n            list.add(new Pair<>(key, map.get(key)));\n        }\n        \n        Integer[][] memo = new Integer[list.size()][sum+1];\n        return helper(l, r, 0, list, 0, memo);\n    }\n\n    int helper(int l, int r, int sum, List<Pair<Integer, Integer>> list, int index, Integer[][]memo) {\n        if (sum > r) return 0;\n        if (index >= list.size()) return sum >= l && sum <= r ? 1 : 0;\n        if(memo[index][sum] != null) return memo[index][sum];\n        Pair<Integer, Integer> pair = list.get(index);\n        int key = pair.getKey(), val = pair.getValue();\n        int res = 0;\n        for (int j = 0; j <= val; j++) {\n            res = (res + helper(l, r, sum + j * key, list, index + 1, memo)) % mod;\n        }\n        return memo[index][sum] = res;\n    }\n}\n```\n\n# DP, knapsack (TLE)\n```\nclass Solution {\n    public int countSubMultisets(List<Integer> nums, int l, int r) {\n        int mod = 1_0000_0000_7;\n        Map<Integer, Integer> map = new HashMap<>();\n        for (int num : nums) {\n            map.put(num, map.getOrDefault(num, 0) + 1);\n        }\n        List<Pair<Integer, Integer>> list = new ArrayList<>();\n        for (int key : map.keySet()) {\n            list.add(new Pair<>(key, map.get(key)));\n        }\n        \n        int[][] dp = new int[list.size()+1][r+1];\n        dp[0][0] = 1;\n        for(int i = 1; i <= list.size(); i++){\n            Pair<Integer, Integer> pair = list.get(i-1);\n            int key = pair.getKey(), val = pair.getValue();\n            for(int j = 0; j <= r; j++){\n                for(int k = 0; k <= val; k++){\n                    if(j - k*key >= 0) dp[i][j] = (dp[i][j] + dp[i-1][j-k*key]) % mod;\n                }\n            }\n        }\n        int res = 0;\n        for(int i = l; i <= r; i++){\n            res = (res + dp[list.size()][i]) % mod;\n        }\n        return res;\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']