Java | TC: O(N*2^N) | SC: O(UniqueNums) | Space Optimized Iterative & Backtracking solutions
Space Optimized Iterative Solution. This solution takes only O(Unique Nums) for countMap\n\njava\n/**\n * Space Optimized Iterative Solution\n *\n * S(n) = (0 \
**Space Optimized Iterative Solution. This solution takes only O(Unique Nums) for countMap**\n\n```java\n/**\n * Space Optimized Iterative Solution\n *\n * S(n) = (0 \xD7 (n C 0) + 1 \xD7 (n C 1) + 2 \xD7 (n C 2) + \u2026 + n \xD7 (n C n))\n * Note that (n C k) = (n C n-k). Therefore:\n * S(n) = 0 \xD7 (n C n) + 1 \xD7 (n C n-1) + 2 \xD7 (n C n-2) + \u2026 + n \xD7 (n C 0)\n * If we add these two together, we get\n * 2S(n) = n \xD7 (n C 0) + n \xD7 (n C 1) + \u2026 + n \xD7 (n C n)\n *       = n \xD7 (n C 0 + n C 1 + \u2026 + n C n)\n * As per binomial theorem, (n C 0 + n C 1 + \u2026 + n C n) = 2^n, so\n * 2*S(n) = n * 2^n => S(n) = n * 2^(n-1)\n *\n * Time Complexity: O(S(N) + n C 0) = O(N * 2^(N-1) + 1) = O(N * 2^N)\n *\n * Space Complexity: O(Unique Nums) (Excluding the result space)\n *\n * N = Length of input nums array\n */\nclass Solution {\n    public List<List<Integer>> subsetsWithDup(int[] nums) {\n        List<List<Integer>> result = new ArrayList<>();\n        if (nums == null) {\n            return result;\n        }\n\n        Map<Integer, Integer> countMap = new HashMap<>();\n        for (int n : nums) {\n            countMap.put(n, countMap.getOrDefault(n, 0) + 1);\n        }\n\n        result.add(new ArrayList<>());\n\n        for (int n : countMap.keySet()) {\n            int size = result.size();\n            int count = countMap.get(n);\n\n            for (int i = 0; i < size; i++) {\n                List<Integer> cur = result.get(i);\n                for (int k = 0; k < count; k++) {\n                    List<Integer> temp = new ArrayList<>(cur);\n                    temp.add(n);\n                    result.add(temp);\n                    cur = temp;\n                }\n            }\n        }\n\n        return result;\n    }\n}\n```\n\n---\n**Backtracking (Recursion). This solution take O(N + Unique Nums) space for recursion depth, temp list and countMap**\n\n```java\n/**\n * Backtracking (Recursion)\n *\n * Time Complexity: O(N * 2 ^ N) Refer to above explanation\n *\n * Space Complexity: O(N + Unique Nums)\n *\n * N = Length of input nums array\n */\nclass Solution1 {\n    public List<List<Integer>> subsetsWithDup(int[] nums) {\n        List<List<Integer>> result = new ArrayList<>();\n        if (nums == null) {\n            return result;\n        }\n\t\t\n\t\t// Avoid sorting by using a count Map\n        Map<Integer, Integer> countMap = new HashMap<>();\n        for (int n : nums) {\n            countMap.put(n, countMap.getOrDefault(n, 0) + 1);\n        }\n\n        subsetsWithDupHelper(countMap, new ArrayList<>(countMap.keySet()), 0, new ArrayList<>(), result);\n        return result;\n    }\n\n    private void subsetsWithDupHelper(Map<Integer, Integer> countMap, List<Integer> uniqueNums,\n\t\t\t\t\t\t\t\t\t  int start, List<Integer> temp, List<List<Integer>> result) {\n        result.add(new ArrayList<>(temp));\n\n        for (int i = start; i < uniqueNums.size(); i++) {\n            int num = uniqueNums.get(i);\n            int count = countMap.get(num);\n            temp.add(num);\n            countMap.put(num, count - 1);\n\n            subsetsWithDupHelper(countMap, uniqueNums, (count == 1 ? i + 1 : i), temp, result);\n\n            countMap.put(num, count);\n            temp.remove(temp.size() - 1);\n        }\n    }\n}\n```\n\n---\n\nSolutions to other Subsets questions on LeetCode:\n- [78. Subsets](https://leetcode.com/problems/subsets/discuss/1549657/Java-or-TC:-O(N*2N)-or-SC:-O(1)-or-Constant-Space-Iterative-and-Backtracking-solutions)\n
['Java']