Leetcode 组合
使用回溯来解决此问题。
提供的代码使用了回溯法（Backtracking），这是一种通过递归探索所有可能解的算法思想。以下是对算法思想的详细解释：
核心思想：
回溯法通过以下步骤解决问题：
- 路径选择：从当前状态出发，尝试所有可能的选项。
- 递归探索：对当前路径进行扩展，继续深入递归以构建更长的路径。
- 回退：如果当前路径无法满足条件（如达到目标长度
k或已遍历完所有可能性），撤销最后的选择并回退到上一步，尝试其他选项。
在这道题中：
- 问题目标：生成从
1到n中长度为k的所有组合。 - 递归逻辑：逐步选择当前范围内的数字，扩展路径，直到路径长度为
k。 - 回溯逻辑：在递归返回时，撤销选择以尝试其他可能性。
代码逐步解析：
-
初始化结果集：
List<List<Integer>> result = new ArrayList<>();result用于存储最终的所有组合结果。 -
调用回溯函数：
backtrack(result, new ArrayList<>(), n, k, 1);result是存储结果的容器。tempList是当前路径，用于记录正在构建的组合。n和k是题目中给定的参数。start是当前搜索的起始数字，避免重复选择。
-
回溯函数的核心逻辑：
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int n, int k, int start) { if (tempList.size() == k) { result.add(new ArrayList<>(tempList)); return; } for (int i = start; i <= n; i++) { tempList.add(i); backtrack(result, tempList, n, k, i + 1); tempList.remove(tempList.size() - 1); } }-
递归终止条件：
if (tempList.size() == k) { result.add(new ArrayList<>(tempList)); return; }如果当前路径
tempList的长度达到了k，将其加入结果集并停止进一步递归。 -
循环遍历生成路径：
for (int i = start; i <= n; i++) { tempList.add(i); // 选择当前数字 backtrack(result, tempList, n, k, i + 1); // 递归，向前扩展路径 tempList.remove(tempList.size() - 1); // 撤销选择，回溯 }每次选择当前数字
i，然后递归地选择下一个数字（从i + 1开始，避免重复）。递归返回后，撤销上一步的选择（即回退一步），尝试其他数字。
-
-
主函数调用：
System.out.println(solution.combine(4, 2)); // 示例1输出 System.out.println(solution.combine(1, 1)); // 示例2输出打印从
1到n中长度为k的所有组合。
算法的时间复杂度分析：
- 状态空间：从
n个数字中选出k个的所有组合，状态空间大小为 ( C(n, k) = \frac{n!}{k!(n-k)!} )。 - 复杂度：
- 回溯会遍历所有可能的组合，每次生成一个组合需要 ( O(k) ) 的时间来构建路径。
- 因此，总时间复杂度为 ( O(k \cdot C(n, k)) )。
算法的优点：
- 高效性：只生成符合条件的路径，避免无效的路径探索。
- 可扩展性：可用于解决类似的组合问题，如排列、子集等。
代码运行过程示例：
以 n = 4, k = 2 为例：
- 初始调用
backtrack([], 1)。 - 递归过程中：
- 选择
1，递归调用backtrack([1], 2)。 - 在选择
1的基础上，依次选择2、3、4，生成组合[1, 2]、[1, 3]、[1, 4]。 - 回退到空路径后，选择
2，依次选择3、4，生成[2, 3]、[2, 4]。 - 继续回退后，选择
3，选择4，生成[3, 4]。
- 选择
- 最终结果为：
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), n, k, 1);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int n, int k, int start) {
if(tempList.size() == k) {
result.add(new ArrayList<>(tempList));
return;
}
//从start开始遍历, 生成所有可能的组合
for(int i = start; i <= n; i++) {
tempList.add(i);
backtrack(result, tempList, n, k, i + 1); //递归生成下一层
tempList.remove(tempList.size() - 1);//撤销上次的选择,tempList.size() - 1应该是元素下标
}
}
}