Simple DP solution


  • 0
    T
    public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    	
    	Set<List<Integer>> set = new HashSet<List<Integer>>();
    	set.add(new LinkedList<Integer>());
    	for (int i=0;i<nums.length;i++) {
    		Set<List<Integer>> set_at_i	 = subsetsAtI(nums,i,set);
    		set = set_at_i;
    	}
    	
    	return new LinkedList<List<Integer>>(set);
    }
    
    Set<List<Integer>> subsetsAtI (int[] nums, int i, Set<List<Integer>> subsets_at_i_1) {
    	List<Integer> newL = new LinkedList<Integer>();
    	newL.add(nums[i]);
    	Set<List<Integer>> ret = new HashSet<List<Integer>>();
    	
    	for (List<Integer> l : subsets_at_i_1) {
    		ret.add(l);
    		List<Integer> ll = new LinkedList<Integer>(l);
    		ll.add(nums[i]);
    		ret.add(ll);
    	}
    	ret.add(newL);
    	return ret;
    }

Log in to reply
 

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