package com.recursion;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;
/**
 * Created by charles on 7/27/16.
 */
public class PermutationII {
    public static ArrayList<ArrayList<Integer>> permuteUnique(ArrayList<Integer> nums) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (nums == null || nums.size() == 0) {
            return res;
        }
        Collections.sort(nums);
        ArrayList<Integer> tmps = new ArrayList<Integer>();
        permuteUniqueHandler(nums, tmps, res, new boolean[nums.size()]);
        return res;
    }

    private static void permuteUniqueHandler(ArrayList<Integer> nums, ArrayList<Integer> tmps,
                                      ArrayList<ArrayList<Integer>> res, boolean[] visited) {
         if (nums.size() == tmps.size()) {
             res.add(new ArrayList(tmps));
             return;
         }
         for (int i = 0; i < nums.size(); i++) {
             if (visited[i] || (i > 0 && !visited[i - 1] && nums.get(i) == nums.get(i - 1))) {
                 System.out.print("i : " + i);
                 System.out.println(" " + visited[i]);
                 System.out.println(Arrays.toString(visited));
                 continue;
             }
             visited[i] = true;
             tmps.add(nums.get(i));
             tmps.stream().forEach(integer -> System.out.print(integer + ", "));
             System.out.println("");
             permuteUniqueHandler(nums, tmps, res, visited);
             tmps.remove(tmps.size() - 1);
             visited[i] = false;
         }
    }

    public static void main(String[] args) {
        ArrayList<Integer> test = new ArrayList<>();
        test.add(1);
        test.add(2);
        test.add(2);
        permuteUnique(test);
    }

}