add a solution for 47

fishercoder1534 · fishercoder1534 · commit a962eed1c760 · 2021-10-18T10:59:17.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_47.java b/src/main/java/com/fishercoder/solutions/_47.java
@@ -2,7 +2,9 @@
 
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.HashSet;
 import java.util.List;
+import java.util.Set;
 
 public class _47 {
     public static class Solution1 {
@@ -15,14 +17,13 @@ public List<List<Integer>> permuteUnique(int[] nums) {
                 return result;
             }
             boolean[] used = new boolean[nums.length];
-            List<Integer> list = new ArrayList();
-            Arrays.sort(nums);
-            dfs(nums, used, list, result);
+            Arrays.sort(nums);//this sorting is critical for the correctness of this backtracking algorithm as we compare the two adjancent neighbors to filter out possible duplicate permutations
+            backtracking(nums, used, new ArrayList(), result);
             return result;
         }
 
 
-        private void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> result) {
+        private void backtracking(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> result) {
             if (list.size() == nums.length) {
                 result.add(new ArrayList(list));
                 return;
@@ -31,20 +32,51 @@ private void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integ
                 if (used[i]) {
                     continue;
                 }
-                if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {
+                if (i > 0 && nums[i - 1] == nums[i] && used[i - 1]) {
+                    /**
+                     * For this line, both !used[i-1] and used[i-1] will AC.
+                     * It is because the first one makes sure when duplicates are selected, the order is ascending (index from small to large).
+                     * However, the second one means the descending order.
+                     * But without this used[i - 1] or !used[i - 1] will not yield a correct result as the program will not yield a correct result.
+                     */
                     continue;
                 }
-                /**
-                 * For this line, both !used[i-1] and used[i-1] will AC. It is because the first one makes sure when
-                 * duplicates are selected, the order is ascending (index from small to large). However,
-                 * the second one means the descending order.
-                 */
                 used[i] = true;
                 list.add(nums[i]);
-                dfs(nums, used, list, result);
+                backtracking(nums, used, list, result);
                 used[i] = false;
                 list.remove(list.size() - 1);
             }
         }
     }
+
+    public static class Solution2 {
+        public List<List<Integer>> permuteUnique(int[] nums) {
+            Arrays.sort(nums);
+            Set<List<Integer>> set = new HashSet<>();
+            set.add(new ArrayList<>());
+            set = recursion(nums, set, 0);
+            List<List<Integer>> res = new ArrayList<>();
+            for (List<Integer> list : set) {
+                res.add(list);
+            }
+            return res;
+        }
+
+        private Set<List<Integer>> recursion(int[] nums, Set<List<Integer>> set, int pos) {
+            if (pos == nums.length) {
+                return set;
+            }
+            Set<List<Integer>> newSet = new HashSet<>();
+            for (List<Integer> list : set) {
+                for (int i = 0; i <= list.size(); i++) {
+                    List<Integer> newList = new ArrayList<>(list);
+                    newList.add(i, nums[pos]);
+                    newSet.add(newList);
+                }
+            }
+            set = newSet;
+            return recursion(nums, set, pos + 1);
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_47Test.java b/src/test/java/com/fishercoder/_47Test.java
@@ -9,17 +9,21 @@
 
 public class _47Test {
     private static _47.Solution1 solution1;
+    private static _47.Solution2 solution2;
     private static List<List<Integer>> actual;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _47.Solution1();
+        solution2 = new _47.Solution2();
     }
 
     @Test
     public void test1() {
         actual = solution1.permuteUnique(new int[]{1, 1, 2});
         CommonUtils.printListList(actual);
+        actual = solution2.permuteUnique(new int[]{1, 1, 2});
+        CommonUtils.printListList(actual);
     }
 
 }

Original file line number	Diff line number	Diff line change
`@@ -9,17 +9,21 @@`
`9`	`9`
`10`	`10`	`public class _47Test {`
`11`	`11`	`private static _47.Solution1 solution1;`
	`12`	`+ private static _47.Solution2 solution2;`
`12`	`13`	`private static List<List<Integer>> actual;`
`13`	`14`
`14`	`15`	`@BeforeClass`
`15`	`16`	`public static void setup() {`
`16`	`17`	`solution1 = new _47.Solution1();`
	`18`	`+ solution2 = new _47.Solution2();`
`17`	`19`	`}`
`18`	`20`
`19`	`21`	`@Test`
`20`	`22`	`public void test1() {`
`21`	`23`	`actual = solution1.permuteUnique(new int[]{1, 1, 2});`
`22`	`24`	`CommonUtils.printListList(actual);`
	`25`	`+ actual = solution2.permuteUnique(new int[]{1, 1, 2});`
	`26`	`+ CommonUtils.printListList(actual);`
`23`	`27`	`}`
`24`	`28`
`25`	`29`	`}`