add a solution for 77

fishercoder1534 · fishercoder1534 · commit ad74745ad532 · 2022-01-24T09:49:46.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_77.java b/src/main/java/com/fishercoder/solutions/_77.java
@@ -31,4 +31,31 @@ private void backtracking(List<Integer> list, int k, int start, int limit, List<
             }
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My completely own solution on 1/24/2022.
+         */
+        public List<List<Integer>> combine(int n, int k) {
+            List<List<Integer>> ans = new ArrayList<>();
+            int[] nums = new int[n];
+            for (int i = 1; i <= n; i++) {
+                nums[i - 1] = i;
+            }
+            backtrack(ans, nums, k, new ArrayList<>(), 0);
+            return ans;
+        }
+
+        private void backtrack(List<List<Integer>> ans, int[] nums, int k, List<Integer> curr, int start) {
+            if (curr.size() == k) {
+                ans.add(new ArrayList<>(curr));
+            } else if (curr.size() < k) {
+                for (int i = start; i < nums.length; i++) {
+                    curr.add(nums[i]);
+                    backtrack(ans, nums, k, curr, i + 1);
+                    curr.remove(curr.size() - 1);
+                }
+            }
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_77Test.java b/src/test/java/com/fishercoder/_77Test.java
@@ -7,14 +7,17 @@
 
 public class _77Test {
     private static _77.Solution1 solution1;
+    private static _77.Solution2 solution2;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _77.Solution1();
+        solution2 = new _77.Solution2();
     }
 
     @Test
     public void test1() {
         CommonUtils.printListList(solution1.combine(4, 2));
+        CommonUtils.printListList(solution2.combine(4, 2));
     }
 }

Original file line number	Diff line number	Diff line change
`@@ -7,14 +7,17 @@`
`7`	`7`
`8`	`8`	`public class _77Test {`
`9`	`9`	`private static _77.Solution1 solution1;`
	`10`	`+ private static _77.Solution2 solution2;`
`10`	`11`
`11`	`12`	`@BeforeClass`
`12`	`13`	`public static void setup() {`
`13`	`14`	`solution1 = new _77.Solution1();`
	`15`	`+ solution2 = new _77.Solution2();`
`14`	`16`	`}`
`15`	`17`
`16`	`18`	`@Test`
`17`	`19`	`public void test1() {`
`18`	`20`	`CommonUtils.printListList(solution1.combine(4, 2));`
	`21`	`+ CommonUtils.printListList(solution2.combine(4, 2));`
`19`	`22`	`}`
`20`	`23`	`}`