Java Solution with Concise Explanation


  • 0
    S

    The idea is naive, there are total 2^n different situation if we don't count the duplicates. Build the recursive tree for adding the current number of not. If there is duplicates, count the number of duplicates, and then based on the the number of duplicates, iteratively call the recurse function with different length of duplicates.

    public class Solution {
    	public List<List<Integer>> subsetsWithDup(int[] nums){
    	    Arrays.sort(nums);
            List<List<Integer>> res = new LinkedList<>();
            recurse(res, nums, 0, new LinkedList<>());
            return res;
    	}
        private void recurse(List<List<Integer>> res, int[] nums, int i, List<Integer> temp){
            if(i==nums.length){
                res.add(temp);
                return;
            }
            if(i<nums.length-1 && nums[i]==nums[i+1]){
                int count = 1;
                 /*count how many duplicates for a specific number*/
                while(i<nums.length-1 && nums[i]==nums[i+1]){
                    count++;
                    i++;
                }
               /*based on the number of duplicates, call recursive with increasing numbers */
                recurse(res, nums, i+1, new LinkedList<>(temp));
                for(int j=0; j<count; j++){
                    List<Integer> newtemp = new LinkedList<>(temp);
                    for(int k=0; k<j+1; k++){
                        newtemp.add(nums[i]);
                    }
                    recurse(res, nums, i+1, newtemp);
                }
                return;
            }
            else{
                /*if there is no duplicates, then we just split the work into two:
                add teh current one or not add the current one.*/
                recurse(res, nums, i+1, new LinkedList<>(temp));
                List<Integer> newtemp = new LinkedList<>(temp);
                newtemp.add(nums[i]);
                recurse(res, nums, i+1, newtemp);
            }
        }
    }

Log in to reply
 

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