Leetcode 组合

使用回溯来解决此问题。

提供的代码使用了回溯法（Backtracking），这是一种通过递归探索所有可能解的算法思想。以下是对算法思想的详细解释：

核心思想：

回溯法通过以下步骤解决问题：

1. 路径选择：从当前状态出发，尝试所有可能的选项。
2. 递归探索：对当前路径进行扩展，继续深入递归以构建更长的路径。
3. 回退：如果当前路径无法满足条件（如达到目标长度 k 或已遍历完所有可能性），撤销最后的选择并回退到上一步，尝试其他选项。

在这道题中：

• 问题目标：生成从 1 到 n 中长度为 k 的所有组合。
• 递归逻辑：逐步选择当前范围内的数字，扩展路径，直到路径长度为 k。
• 回溯逻辑：在递归返回时，撤销选择以尝试其他可能性。

代码逐步解析：

1. 初始化结果集：

   List<List<Integer>> result = new ArrayList<>();
   

   result 用于存储最终的所有组合结果。

2. 调用回溯函数：

   backtrack(result, new ArrayList<>(), n, k, 1);
   

   • result 是存储结果的容器。
   • tempList 是当前路径，用于记录正在构建的组合。
   • n 和 k 是题目中给定的参数。
   • start 是当前搜索的起始数字，避免重复选择。

3. 回溯函数的核心逻辑：

   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 开始，避免重复）。递归返回后，撤销上一步的选择（即回退一步），尝试其他数字。

4. 主函数调用：

   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 为例：

1. 初始调用 backtrack([], 1)。
2. 递归过程中：
   • 选择 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]。
3. 最终结果为：

   [[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应该是元素下标
        }
    }
}