Array Subsets Duplicate Elements LeetCode (Power Set of Elements in an Array)

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

 Example 1:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

 

NOTE:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

 This problem is popular in LeetCode and GeeksForGeeks

Solution:

 

	/**
	ArrayWithDuplicateSubsets
	Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
	Note: The solution set must not contain duplicate subsets.
	Example:
	Input: [1,2,2]
	Output:
	[
	[2],
	[1],
	[1,2,2],
	[2,2],
	[1,2],
	[]
	]
	*/
	import java.util.*;
	public class ArraySubsetsDuplicateElements{
	public static List<List<Integer>> subsetsWithDup(int[] nums) {
	//handle base case
	List<List<Integer>> lists = new ArrayList<List<Integer>>();
	Arrays.sort(nums);
	subsetRecursive(lists, new ArrayList<Integer> (), nums, 0);
	return lists;
	}
	public static void subsetRecursive(List<List<Integer>> lists, List<Integer> tempList, int[] nums, int start){
	lists.add(new ArrayList<>(tempList));
	for(int i=start; i<nums.length; i++){
	//skip duplicates
	if(i>start && nums[i]==nums[i-1]) continue;
	tempList.add(nums[i]);
	subsetRecursive(lists, tempList, nums, i+1);
	tempList.remove(tempList.size()-1);
	}
	}
	/**
	public static List<List<Integer>> subsetsWithDup(int[] nums) {
	//handle base case
	List<List<Integer>> sets = new ArrayList<List<Integer>>();
	sets.add(new ArrayList<Integer>());
	if(nums.length==0){
	return sets;//empty set
	}
	Arrays.sort(nums);
	for(int i=0;i<nums.length; i++){
	int size = sets.size();
	for(int j=0;j<size; j++){
	//TODO: handle duplicates
	List<Integer> newlist = new ArrayList<>(sets.get(j));
	newlist.add(nums[i]);
	sets.add(newlist);
	}
	}
	return sets;
	}
	*/
	public static void main(String[] args){
	int[] nums = new int[]{1,2,2};
	nums = new int[]{1,1,2,2};
	List<List<Integer>> sets = subsetsWithDup(nums);
	for(List<Integer> list:sets){
	System.out.println(Arrays.toString(list.toArray(new Integer[list.size()])));
	}
	}
	}

view raw ArraySubsetsDuplicateElements.java hosted with ❤ by GitHub