Subsets II @LeetCode

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

	package leetcode.combinations;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	*
	* @author jeffwan
	* @date Feb 10, 2014
	*
	* Thought -- number2 can't selected before number1, i>=position.abort number2 when i> position
	*
	* Almost same to subset I, only difference is if() to skip the duplicate
	* i == position --> go depth, when we add number, we don't care duplicates
	* i != position means back tracking, already remove one number, i++ which leads i!=position,(i>position also works)
	* that means second or third or more time, we care about the duplicate numbers. As they are sorted, we abort and continue.
	*
	*/
	public class Subsets2 {
	public static void main(String[] args) {
	int[] S = {1, 2, 2, 2};
	System.out.println(subsetsWithDup(S));
	}
	public static ArrayList<ArrayList<Integer>> subsetsWithDup (int[] num) {
	Arrays.sort(num);
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	subsetsWithDupHelper(result, list, num, 0);
	return result;
	}
	private static void subsetsWithDupHelper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, int[] num, int position) {
	result.add(new ArrayList<Integer>(list));
	for (int i = position; i < num.length; i++) {
	if (i != position && num[i] == num[i-1]){
	continue;
	}
	list.add(num[i]);
	subsetsWithDupHelper(result, list, num, i+1);
	list.remove(list.size() - 1);
	}
	}
	}

view raw Subsets2.java hosted with ❤ by GitHub