week03 second commit

herost789 · herost789 · commit dc25bbaf1640 · 2020-06-28T23:28:24.000+08:00
diff --git a/Week03/NOTE.md b/Week03/NOTE.md
@@ -33,6 +33,19 @@
 	}
 #####递归思维要点
 	1.不要进行人肉递归(最大误区)
-	2.找到最近最简方法，将其拆解成可重复解决的问题(重复子问题)
+	2.找到最近最简方法，将其拆解成可重复解决的问题
+	(重复子问题)
 	3.数学归纳法的思维
-#####分治回溯就是一种特殊的递归或者是较为复杂的递归
+#####分治回溯就是一种特殊的递归或者是较为复杂的递归
+按照DFS算法的策略，从跟结点出发搜索解空间树。首先根
+结点成为活结点（指自身已生成但其孩子结点没有全部生
+成的结点），同时也成为当前的扩展结点（指正在产生孩
+子结点的结点）
+在当前的扩展结点处，搜索向纵深方向移至一个新结点。
+这个新结点就成为新的活结点，并成为当前扩展结点。
+如果在当前的扩展结点处不能再向纵深方向移动，则当
+前扩展结点就成了死结点（指其所有子结点均已产生的结
+点）。此时应往回移动（回溯）至最近的一个活结点处，
+并使这个活结点成为当前的扩展结点。回溯法以这种方式
+递归地在解空间中搜索，直到找到所要求的解或解空间中
+已无活结点为止。
diff --git a/Week03/com/myhomework/Combine.java b/Week03/com/myhomework/Combine.java
@@ -0,0 +1,34 @@
+package com.myhomework;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Stack;
+
+public class Combine {
+    private List<List<Integer>> res = new ArrayList<>();
+
+    private void findCombinations(int n, int k, int begin, Stack<Integer> pre) {
+        if (pre.size() == k) {
+            // 够数了，就添加到结果集中
+            res.add(new ArrayList<>(pre));
+            return;
+        }
+        // 关键在于分析出 i 的上界
+        for (int i = begin; i <= n; i++) {
+            pre.add(i);
+            findCombinations(n, k, i + 1, pre);
+            pre.pop();
+        }
+    }
+
+    public List<List<Integer>> combine(int n, int k) {
+        // 特判
+        if (n <= 0 || k <= 0 || n < k) {
+            return res;
+        }
+        // 从 1 开始是题目的设定
+        findCombinations(n, k, 1, new Stack<>());
+        return res;
+    }
+
+}
