package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode.com/problems/permutations-ii/
 */
public class Problem47 {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        for (int n : nums) {
            list.add(n);
        }
        List<Integer> accu = new ArrayList<>();
        Set<List<Integer>> tmpResult = new HashSet<>();
        permutation(list, accu, tmpResult);
        result.addAll(tmpResult);
        return result;
    }

    private void permutation(List<Integer> nums, List<Integer> accu, Set<List<Integer>> result) {
        if (nums.size() == 0) {
            result.add(accu);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            List<Integer> newList = new ArrayList<>();
            for (int j = 0; j < nums.size(); j++) {
                if (i == j) {
                    continue;
                }
                newList.add(nums.get(j));
            }
            List<Integer> newAccu = new ArrayList<>(accu);
            newAccu.add(nums.get(i));
            permutation(newList, newAccu, result);
        }
    }

    public static void main(String[] args) {
        Problem47 prob = new Problem47();
//        List<List<Integer>> result = prob.permuteUnique(new int[]{1, 1, 2});
//        List<List<Integer>> result = prob.permuteUnique(new int[]{3, 3, 0, 0, 2, 3, 2});
        List<List<Integer>> result = prob.permuteUnique(new int[]{1, 1, 0, 0, 1, -1, -1, 1});
        for (List<Integer> list : result) {
            System.out.println(list);
        }
    }
}

@@ -36,24 +36,49 @@
 .ArrayList;%0A
+import java.util.Arrays;%0A
 import java.
@@ -327,32 +327,59 @@
  ArrayList%3C%3E();%0A
+        Arrays.sort(nums);%0A
         List%3CInt
@@ -534,126 +534,33 @@
     
-Set%3CList%3CInteger%3E%3E tmpResult = new HashSet%3C%3E();%0A        permutation(list, accu, tmpResult);%0A        result.addAll(tmpR
+permutation(list, accu, r
 esul
@@ -662,18 +662,19 @@
 %3E accu, 
-Se
+Lis
 t%3CList%3CI
@@ -776,32 +776,82 @@
 turn;%0A        %7D%0A
+        Set%3CString%3E duplicates = new HashSet%3C%3E();%0A
         for (int
@@ -929,32 +929,84 @@
  ArrayList%3C%3E();%0A
+            StringBuilder sb = new StringBuilder();%0A
             for 
@@ -1111,32 +1111,78 @@
               %7D%0A
+                sb.append(nums.get(j) + %22%7C%22);%0A
                 
@@ -1237,144 +1237,106 @@
     
-List%3CInteger%3E newAccu = new ArrayList%3C%3E(accu);%0A            newAccu.add(nums.get(i));%0A            permutation(newList, newAccu, result);%0A
+String s = sb.toString();%0A            if (duplicates.contains(s)) %7B%0A                continue;%0A    
     
@@ -1349,187 +1349,102 @@
     
+  
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem47 prob = new Problem47();%0A//        List%3CList%3CInteger%3E%3E result = prob.permuteUnique(new int%5B%5D%7B1, 1, 2%7D
+  duplicates.add(s);%0A            List%3CInteger%3E newAccu = new ArrayList%3C%3E(accu
 );%0A
-//
         
 List
@@ -1443,261 +1443,85 @@
     
-List%3CList%3CInteger%3E%3E result = prob.permuteUnique(new int%5B%5D%7B3, 3, 0, 0, 2, 3, 2%7D);%0A        List%3CList%3CInteger%3E%3E result = prob.permuteUnique(new int%5B%5D%7B1, 1, 0, 0, 1, -1, -1, 1%7D);%0A        for (List%3CInteger%3E list : result) %7B%0A            System.out.println(lis
+    newAccu.add(nums.get(i));%0A            permutation(newList, newAccu, resul
 t);%0A

Solve problem 47