Given a set of distinct integers, nums, return all possible subsets but handle duplicates.


https://leetcode.com/problems/subsets/

Consider example [1,1,2] returns [], [1], [2], [1,2], [1,1,2]


The problem is classic example of backtracking. It is similar to Subsets Problem. The code here is pretty much similar with a major single line difference.

public class SubSet {

	public List> subsets(int[] nums) {
       Arrays.sort(nums);
		List<List<Integer>> l = new ArrayList();
		for (int i = 0; i <= nums.length; i++) {
			subsets(nums, i, l, 0, new ArrayList());
		}
		return l;
	}

	private void subsets(int[] nums, int currLength, List<List<Integer>> l,
	 int start, List<Integer> curr) {
		if (curr.size() == currLength) {
			l.add(new ArrayList(curr));
			return;
		}
		for(int i = start; i < nums.length; i++) {
			//ignore if element is already visited
			if (i != start && nums[i - 1] == nums[i])
				continue;
			}
			curr.add(nums[i]);
			subsets(nums, currLength, l, i+1, curr);
			curr.remove(curr.size() - 1);
		}
}	

Subscribe to get latest updates.

© 2016 Java Questions | Sitemap