package leetcode.combinations;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Thought: Almost same as Permutation. Only difference is to remove duplicates. 
 * if number1 equals number2, defaultly, we get the number1, abort number2, so  
 * number2 can't be used if the number1 haven't be used.
 *  
 * In subset, we have a position marker and sorted int array. As we don't have position now, we could 
 * use a flag array instead.
 * 
 * @author jeffwan
 * @date Feb 10, 2014
 */
public class Permutations2 {
	
	public static void main(String[] args) {
		int[] num = {1, 1, 2};
		System.out.println(permuteUnique(num));
	}
	
	
	public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
		Arrays.sort(num);
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		boolean[] visited = new boolean[num.length];

		permuteUniqueHelper(result, list, num, visited);

		return result;
	}


	private static void permuteUniqueHelper(ArrayList<ArrayList<Integer>> result,
			ArrayList<Integer> list, int[] num, boolean[] visited) {

		if (list.size() == num.length) {
			result.add(new ArrayList<Integer>(list));
			return;
		}

		for (int i=0; i<num.length; i++) {
			if (visited[i]==true || (i!=0 && num[i] == num[i-1] && visited[i-1] == false)) {
				continue;
			}

			visited[i] = true;
			list.add(num[i]);
			permuteUniqueHelper(result, list, num, visited);
			list.remove(list.size() - 1);
			visited[i] = false;
		}

	}
	
}