O(2^n) Simple Java Solution


  • 0
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> L = new ArrayList<List<Integer>>();
        L.add(new ArrayList<Integer>());
        Arrays.sort(nums);
        subsetsWithDup(nums,L,new ArrayList<Integer>(),0);
        return L;
    }
    		
    private void subsetsWithDup(int[] nums,List<List<Integer>> L,List<Integer> currentList,int start){
        if (start >= nums.length) return;
        
        int prevNum = Integer.MIN_VALUE;
        for (int i=start;i<nums.length;i++){
            if (prevNum != nums[i]){
                currentList.add(nums[i]);
                L.add(new ArrayList<Integer>(currentList));
                subsetsWithDup(nums,L,currentList,i+1);
                currentList.remove((int)currentList.size()-1);
            }
            prevNum = nums[i];
        }
    }

Log in to reply
 

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