Easy java solution


  • 0
    S
    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            
            List<List<Integer>> result = new LinkedList<List<Integer>>();
            int len = nums.length;
            
            List<Integer> uNums = new LinkedList<Integer>();
            HashMap<Integer,Integer> countMap = new HashMap<Integer,Integer>();
            
            for(int i=0;i<len;i++) {
                Integer count = countMap.get(nums[i]);
                
                if(count == null) {
                    uNums.add(nums[i]);
                    countMap.put(nums[i] , 1);
                } else {
                    countMap.put(nums[i] , count + 1);
                }
            }
            
            Collections.sort(uNums);
            
            build(result, uNums, new LinkedList<Integer>(), countMap, 0);
            
            return result;
        }
        
        public void build(List<List<Integer>> result, List<Integer> nums, List<Integer> cur, HashMap<Integer,Integer> countMap, int index) {
            
            if(index == nums.size()) {
                result.add(cur);
                return;
            }
            
            Integer num = nums.get(index);
            Integer count = countMap.get(num);
            
            List<Integer> emptyList = new LinkedList<Integer>(cur);
            build(result, nums, emptyList, countMap, index + 1);
            
            for(int i=0;i<count;i++) {
                cur.add(num);
                List<Integer> list = new LinkedList<Integer>(cur);
                build(result, nums, list, countMap, index + 1);
            }
        } 
    }

Log in to reply
 

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