Another easy understand java solution with extra O(n) space (HashMap)


  • 0
    R
    • the main idea is using a list to maintain the unique nums, and a map to save the counts of each num. then the problem becomes to a subset without duplicated.
    • In the subset without duplicated problem, each num has two choice(pick or not), but it also can be thought as pick none, one, two,....count ,so it's the same as this duplicated problem
    • I maintain another uniqueNums list just to make this solution easier to understand.
    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            HashMap<Integer, Integer> map = new HashMap<>();
            ArrayList<Integer> uniqueNums = new ArrayList<>();
            for (int num: nums) {
                if (map.containsKey(num)) {
                    int count = map.get(num);
                    map.put(num, count + 1);
                }
                else {
                    uniqueNums.add(num);
                    map.put(num, 1);
                }
            }
            List<List<Integer>> results = new ArrayList<>();
            this.subSets(uniqueNums, 0, map, results, new ArrayList<Integer>());
            return results;
        }
        
        private void subSets(List<Integer> uniqueNums, int curIndex, Map<Integer, Integer> map, List<List<Integer>> results, List<Integer> curResult) {
            if (curIndex >= uniqueNums.size()) {
                results.add(new ArrayList<>(curResult));
                return;
            }
            int curNumber = uniqueNums.get(curIndex);
            int count = map.get(curNumber);
            for (int addCount = 0; addCount <= count; addCount++) {
                for (int i = 0; i < addCount; i++) {
                    curResult.add(curNumber);
                }
                this.subSets(uniqueNums, curIndex + 1, map, results, curResult);
                for (int i = 0; i < addCount; i++) {
                    curResult.remove(curResult.size() - 1);
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.