*Java* straightforward iterative solution (4ms)


  • 0
    E

    Key ideas:

    • sort the array
    • store obtained list up to index i (exclusive)
    • for index i, skip all values equal to i and count number of skipped items. Consider all items with same value one block and process all of them at once
    • It's now a simple math combination problem: from 0 to i-1, we have a list of results res, at i (after skipping duplicates), we have another list of results innerList, just add all combinations of res and innerList

    For example,

    e.g., nums = [1, 2, 3, 3, ...]
    before i=2, we have res = [[ ], [1], [2], [1,2]]
    when i=2, skip value 3 and move i to index 3, skipped indices=1
    innerList = [[ ], [3], [3,3]]
    add all combinations of `res` and `innerList` and the outcome becomes the new res
    

    Code in Java:

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);   
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> innerList = new ArrayList<Integer>();
        res.add(innerList);
        for(int i=0, L=nums.length; i<L; i++) {
        	int skipped = 0; // number of duplicate values
    		while(i+1<L && nums[i]==nums[i+1]) { // skip duplicates
    			++skipped;
    			++i;
    		}
    		
    		List<List<Integer>> newList = new ArrayList<List<Integer>>(); // to store new result including i;
    		for(List<Integer> left : res) {
    			newList.add(left);
    			innerList = new ArrayList<Integer>();
    			for(int j=0; j<=skipped; j++) { // add all duplicate values
    				List<Integer> combined = new ArrayList<Integer>(left);
    				innerList.add(nums[i-j]);
    				combined.addAll(innerList);
    				newList.add(combined);
    			}
    		}
    		res = newList; // update res
    	}
        return res;
    }

Log in to reply
 

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